Tehtävä:
Backus–Naur Format

Tarkastellaan ensin, mitä merkkijonoja alla määriteltyihin kieliin kuuluu.

A::=B | A B
B::=”(” ”)” | ”(” A ”)”

Aluksi emme tiedä yhtään kumpaankaan kieleen kuuluvaa merkkijonoa, joten emme pysty tuottamaan mitään vaihtoehdoilla A ::= B, A ::= A B ja B ::= ”(” A ”)”. Vaihtoehdolla B ::= ”(” ”)” saamme B:hen merkkijonon ”()”, mitä merkitsemme lyhyemmin ”()” ∈ B. Nyt kun olemme löytäneet B:hen kuuluvan merkkijonon, saamme säännöllä A ::= B tulokseksi ”()” ∈ A. Sen avulla A ::= A B tuottaa ”()()” ∈ A ja B := ”(” A ”)” tuottaa ”(())” ∈ B. Säännöllä A ::= A B saadaan nyt ”()(())” ∈ A, ”()()()” ∈ A ja ”()()(())” ∈ A. Koska ”()()” ∈ A, B := ”(” A ”)” tuottaa ”(()())” ∈ B. Uusia merkkijonoja tulee loputtomiin, mutta vain sellaisia, joissa alku- ja loppusulut täsmäävät ja mitään muuta niissä ei olekaan.

Tarkastellaan seuraavaa kielioppia:

Lauseke::=Tulo | Lauseke ”+” Tulo | Lauseke ”−” Tulo
Tulo::=Tekijä | Tulo ”·” Tekijä | Tulo ”/” Tekijä
Tekijä::=Atomi | ”+” Atomi | ”−” Tekijä
Atomi::=Luku | Muuttuja | ”(” Lauseke ”)”

”Luku” on epätyhjä jono numeroita ja ”Muuttuja” on kirjain. Klikkaa ruudut sen mukaan mihin kieliin rivin alun merkkijono kuuluu. Rivin ensim­mäinen ruutu vastaa atomia, toinen tekijää, kolmas tuloa ja neljäs lauseketta.

6
tai
(
tai
−x
tai
+x
tai
−−x
tai
+−x
tai
2·x·y
tai
−2·+x·y
tai
3x
tai
x−x
tai
+1++1
tai
(3·x+1)
tai

Olkoon A ::= ”0” | ”1” ja B ::= A | A B. Lyhenne ”n.y.k.” tarkoittaa ”nollista ja / tai ykkösistä koostuvat”. Mitkä seuraavista pitävät paikkansa?
A on kaikki n.y.k. jonot.
A on kaikki n.y.k. epätyhjät jonot.
A on kaikki n.y.k. jonot pituudeltaan 1.
B on kaikki n.y.k. jonot.
B on kaikki n.y.k. epätyhjät jonot.
B on kaikki n.y.k. jonot pituudeltaan 1.
tai

Mitkä seuraavista pitävät paikkansa?
A sisältää ainakin kaikki n.y.k. jonot.
A sisältää ainakin kaikki n.y.k. epätyhjät jonot.
A sisältää ainakin kaikki n.y.k. jonot pituudeltaan 1.
B sisältää ainakin kaikki n.y.k. jonot.
B sisältää ainakin kaikki n.y.k. epätyhjät jonot.
B sisältää ainakin kaikki n.y.k. jonot pituudeltaan 1.
tai

Olkoon C ::= A | ε. Mitkä seuraavista sisältävät kaikki n.y.k. jonot?
X ::= A | X A
X ::= A | X C
X ::= C | X A
X ::= C | X C
tai

Mitkä seuraavista kieliopeista määrittelevät ne n.y.k. vähintään kolme merkkiä pitkät jonot, joiden ensim­mäinen ja viimeinen merkki ovat samat?
P ::= A B A
P ::= ”0” B ”0” | ”1” B ”1”
tai

Mitkä seuraavista kieliopeista määrittelevät n.y.k. palindromit eli n.y.k. jonot, jotka ovat samoja etuperin ja takaperin?
P ::= A | A P A
P ::= C | A P A
P ::= ε | ”0” P ”0” | ”1” P ”1”
P ::= A | ”0” P ”0” | ”1” P ”1”
P ::= C | ”0” P ”0” | ”1” P ”1”
P ::= ”0” | ”1” | ”0” P ”0” | ”1” P ”1”
P ::= ε | ”0” | ”1” | ”0” P ”0” | ”1” P ”1”
tai

Varaudu määrittelemään BNF:llä seuraavat kielet: