Samenvatting Hoofdstuk 4: Eigenschappen van Reguliere Talen

Hoofdstuk 4: Eigenschappen van reguliere
talen
1 Eigenschappen
• Zijn alle talen regulier?
• Indien we 2 reguliere talen combineren, krijgen we dan een nieuwe reguliere taal?
• Hoe kunnen we aantonen dat een taal regulier is?
• Hoe kunnen we aantonen dat een taal niet regulier is?

1.1 Closure under simple set operations
Eigenschap:
Als 𝐿1 en 𝐿2 reguliere talen zijn, dan zijn 𝐿1 ∪ 𝐿2 , 𝐿1 ∩ 𝐿2 , 𝐿1 𝐿2 , ̅̅̅̅
𝐿1 en 𝐿∗1 ook reguliere talen.

Bewijs:




1

, Voorbeeld:




1.2 Closure under reversal
Eigenschap:
The family of regular languages is closed under reversal.

Bewijs:




1.3 Other closure properties
• Closed under arbitrary homomorphisms
o Replace each symbol in vocabulary by a certain string
• Closed under right quotient
𝐿1
o 𝐿2
= {𝑥: 𝑥𝑦 ∈ 𝐿1 𝑓𝑜𝑟 𝑠𝑜𝑚𝑒 𝑦 ∈ 𝐿2 }


2 Elementary questions about regular languages




2