Göm menyn

Seminarium 9 - En sak i taget

Kapitel att läsa inför

Uppgift: Backus-Neur-Form

Givet är språk i Backus-Neur-Form. Språken innehåller endast bokstäverna 'a' och 'b', dessa kallas terminaler som i avslutande. Stora bokstäver är så kallade 'icke-terminaler' och för att få fram ett ord måste samtliga icke-terminaler ersättas med terminaler. Tecknet '|' betyder 'eller'. Tecknet 'e' betyder 'inget', dvs att en icke-terminal kan tas bort.

Icke-terminalen 'S' är startsymbolen för språket.

Vissa sekvenser av bokstäverna ingår i språken, vissa gör det inte. Ange vilka sekvenser (ord) som ingår i språken.

Denna sortens språk studeras vidare i kursen Formella språk och automatateori (master-kurs för D, obligatorisk kurs för U)

1

Exempel

Språket innehåller följande sekvenser: 'a', 'aa', 'ab', 'b', 'ba', 'bb'

Uppgift: Identifiera ord

Skriv pythonkod som identifierar om en given sträng ingår i språk 1 respektive språk 2 i uppgiften 'Backus-Neur-Form'


Sidansvarig: Peter Dalenius
Senast uppdaterad: 2016-08-17