Hoofdstuk 1: Languages, grammars en
automata
1 (Formal) Languages
• Alphabet Σ = {𝑎, 𝑏} met a en b symbolen
o 𝑢 = 𝑎𝑏𝑎𝑎, 𝑣 = 𝑏𝑎𝑏, … zijn strings, 𝜆 stelt de lege string voor
▪ Merk op dat de lege string en de lege verzameling niet hetzelfde zijn!
o Reverse 𝑢𝑅 = 𝑎𝑎𝑏𝑎
o Concatenatie 𝑢𝑣 = 𝑎𝑏𝑎𝑎𝑏𝑎𝑏
o Lengte |𝑢| = 4, |λ| = 0
• Star closure Σ ∗ = {𝜆, 𝑎, 𝑏, 𝑎𝑎, 𝑎𝑏, 𝑏𝑎, 𝑏𝑏 … }
o De start closure van het alfabet sigma is de verzameling strings die gemaakt kunnen
worden door de symbolen uit sigma met elkaar te combineren.
• Een taal over alfabet sigma is een subset van Σ ∗
o Voorbeeld taal over sigma: 𝐿 = {𝑎 𝑛𝑏 𝑛 :𝑛 ≥ 0}
• We noemen u een substring van uv.
1.1 Operaties over talen
Stel Σ is een alfabet en L, L1, L2 zijn talen over Σ.
• Het complement van L : 𝐿̅ = Σ ∗ − 𝐿
• Het omgekeerde van 𝐿: 𝐿𝑅 = {𝑤 𝑅 : 𝑤 ∈ 𝐿}
o Stel 𝐿 = {𝑎, 𝑏, 𝑎𝑎𝑏}, dan is 𝐿𝑅 = {𝑎, 𝑏, 𝑏𝑎𝑎}
• De concatenatie van L1 en L2: 𝐿1 𝐿2 = {𝑢𝑣:𝑢 ∈ 𝐿1 , 𝑣 ∈ 𝐿2 }
• 𝐿𝑛 = 𝐿𝐿 … 𝐿, 𝑛 𝑘𝑒𝑒𝑟 met 𝐿0 = {𝜆}
o 𝐿0 wordt namelijk gevormd door 0 strings uit L aan elkaar te plakken.
• 𝐿∗ = 𝐿0 ∪ 𝐿1 ∪ 𝐿2 ∪ …
1.2 Talen beschrijven
• Wiskundig: 𝐿 = {𝑎 𝑛 𝑏𝑛 :𝑛 ≥ 0}
• Met woorden: “Alle strings bestaande uit een aantal a’s, gevolgd door hetzelfde aantal b’s.”
• Met een programma/automaat die test of een bepaalde string (invoer) tot L behoort.
• Met een programma dat alle strings behorende tot L opsomt.
• Gebruikmakende van een grammatica.
Kunnen we deze voorstellingen gebruiken om (automatisch) na te gaan of een string tot L behoort,
om alle strings uit L te genereren of om voor een taal L’ na te gaan of L=L’?
1.3 Grammatica
Een grammatica is een 4-tuple: 𝐺 = {𝑉, 𝑇, 𝑆, 𝑃}
• V is een verzameling van variabelen
• T is een verzameling terminal symbols
• S is een startvariabele
• P is een verzameling producties
o Wat zijn producties??
1
automata
1 (Formal) Languages
• Alphabet Σ = {𝑎, 𝑏} met a en b symbolen
o 𝑢 = 𝑎𝑏𝑎𝑎, 𝑣 = 𝑏𝑎𝑏, … zijn strings, 𝜆 stelt de lege string voor
▪ Merk op dat de lege string en de lege verzameling niet hetzelfde zijn!
o Reverse 𝑢𝑅 = 𝑎𝑎𝑏𝑎
o Concatenatie 𝑢𝑣 = 𝑎𝑏𝑎𝑎𝑏𝑎𝑏
o Lengte |𝑢| = 4, |λ| = 0
• Star closure Σ ∗ = {𝜆, 𝑎, 𝑏, 𝑎𝑎, 𝑎𝑏, 𝑏𝑎, 𝑏𝑏 … }
o De start closure van het alfabet sigma is de verzameling strings die gemaakt kunnen
worden door de symbolen uit sigma met elkaar te combineren.
• Een taal over alfabet sigma is een subset van Σ ∗
o Voorbeeld taal over sigma: 𝐿 = {𝑎 𝑛𝑏 𝑛 :𝑛 ≥ 0}
• We noemen u een substring van uv.
1.1 Operaties over talen
Stel Σ is een alfabet en L, L1, L2 zijn talen over Σ.
• Het complement van L : 𝐿̅ = Σ ∗ − 𝐿
• Het omgekeerde van 𝐿: 𝐿𝑅 = {𝑤 𝑅 : 𝑤 ∈ 𝐿}
o Stel 𝐿 = {𝑎, 𝑏, 𝑎𝑎𝑏}, dan is 𝐿𝑅 = {𝑎, 𝑏, 𝑏𝑎𝑎}
• De concatenatie van L1 en L2: 𝐿1 𝐿2 = {𝑢𝑣:𝑢 ∈ 𝐿1 , 𝑣 ∈ 𝐿2 }
• 𝐿𝑛 = 𝐿𝐿 … 𝐿, 𝑛 𝑘𝑒𝑒𝑟 met 𝐿0 = {𝜆}
o 𝐿0 wordt namelijk gevormd door 0 strings uit L aan elkaar te plakken.
• 𝐿∗ = 𝐿0 ∪ 𝐿1 ∪ 𝐿2 ∪ …
1.2 Talen beschrijven
• Wiskundig: 𝐿 = {𝑎 𝑛 𝑏𝑛 :𝑛 ≥ 0}
• Met woorden: “Alle strings bestaande uit een aantal a’s, gevolgd door hetzelfde aantal b’s.”
• Met een programma/automaat die test of een bepaalde string (invoer) tot L behoort.
• Met een programma dat alle strings behorende tot L opsomt.
• Gebruikmakende van een grammatica.
Kunnen we deze voorstellingen gebruiken om (automatisch) na te gaan of een string tot L behoort,
om alle strings uit L te genereren of om voor een taal L’ na te gaan of L=L’?
1.3 Grammatica
Een grammatica is een 4-tuple: 𝐺 = {𝑉, 𝑇, 𝑆, 𝑃}
• V is een verzameling van variabelen
• T is een verzameling terminal symbols
• S is een startvariabele
• P is een verzameling producties
o Wat zijn producties??
1
