KOI: Exercise 2: Grammars and languages

You can do this exercise in any size group you wish. Don't worry if you find some of the questions difficult to answer, since they may be intended to initiate a discussion rather than have a single correct answer.

Preparations

Before this exercise you should have:

Uppgift 1

Ett språk innehåller terminalerna god, morgon, middag och kväll. Grammatiken för språket innehåller icke-terminalerna hälsning och tidsspecifikation, och följande produktioner: 
hälsning -> god tidsspecifikation
tidsspecifikation -> morgon
tidsspecifikation -> middag
tidsspecifikation -> kväll
tidsspecifikation -> god
Startsymbolen är hälsning.

Ange vilket språk grammatiken beskriver, genom att räkna upp alla strängar (dvs sekvenser av terminaler) som kan uttryckas i språket.

Hur fick du fram svaret?

Uppgift 2

Här är en lite annorlunda grammatik: 
flera-hälsningar -> hälsning
flera-hälsningar -> hälsning flera-hälsningar
hälsning -> god tidsspecifikation
tidsspecifikation -> morgon
tidsspecifikation -> middag
tidsspecifikation -> kväll
tidsspecifikation -> god
Startsymbolen är flera-hälsningar.

Vilket språk beskriver den grammatiken?

Uppgift 3

Här är en tredje grammatik: 
tidsspecifikation -> båt | båt tidsspecifikation
båt -> god flera-hälsningar
flera-hälsningar -> morgon | middag | kväll | god
Startsymbolen är tidsspecifikation.

a) Vilket språk beskriver den grammatiken?

b) Vilka lärdomar kan man få av den här uppgiften?

Ett scenario

Vi ska skriva ett program där man kan mata in dessa "helghälsningar": En komplett inmatning består av en eller flera sådana hälsningar, och avslutas med "Klart!". Exempel: 

God Jul!
God Jul!
God Jul!
Trevlig Midsommar!
Glad Påsk!
Klart!

Uppgift 4

Vilka terminaler behövs för att man ska kunna skriva en grammatik för språket?

Uppgift 5

Skriv en grammatik för en hälsning i det beskrivna språket. Startsymbolen ska vara hälsning, som representerar en sådan hälsning.

Uppgift 6

Skriv en grammatik för hälsningsspråket som beskrivs i scenariot. Startsymbolen ska vara inmatning, som representerar en fullständig inmatning enligt scenariot ovan. Den ska alltså motsvara en eller flera hälsningar, följt av "Klart!".

Ledtråd: Gör en icke-terminal som heter flera-hälsningar, som representerar en eller flera hälsningar. Flera-hälsningar kan då vara antingen en ensam hälsning, eller en ensam hälsning följd av flera hälsningar.

Thomas Padron-McCarthy (thomas.padron-mccarthy@oru.se), September 19, 2021