Hoofdstuk 7: Pushdown automaten
1 Automaten voor context-vrije talen
Voorbeelden:
𝐿 = {𝑎𝑛 𝑏𝑛 |𝑛 ≥ 0} → eindig geheugen is niet geschikt om bij te houden hoe veel a’s er tot nu toe
verwerkt zijn en dan even veel b’s toe te voegen.
𝐿 = {𝑤𝑤 𝑅 |𝑤 ∈ {𝑎, 𝑏}} → we hebben de mogelijkheid nodig om de sequentie karakters op te slaan
en in omgekeerde volgorde opnieuw te overlopen
Het idee:
Voeg een stack (vorm van geheugen) toe aan de
automaten die we tot nu toe gebruikt hebben
2 Nondeterministic pushdown
accepter (npda)
Definitie:
Een niet-deterministische pushdown accepter (npda)
wordt gedefinieerd door het tuple 𝑀 =
(𝑄, Σ, Γ, δ, 𝑞0 , 𝑧, 𝐹). Hierbij is
• Q een eindige verzameling interne toestanden (states) van de accepter.
• sigma het alfabet
• gamma een eindige verzameling symbolen die we het stack alfabet noemen
• 𝛿: 𝑄 × (Σ ∪ {𝜆}) × Γ → 𝑒𝑖𝑛𝑑𝑖𝑔𝑒 𝑑𝑒𝑒𝑙𝑣𝑒𝑟𝑧𝑎𝑚𝑒𝑙𝑖𝑛𝑔 𝑣𝑎𝑛 𝑄 × Γ ∗ de transitiefunctie
• 𝑞0 ∈ 𝑄 de initiële staat van de accepter
• 𝑧 ∈ Γ het startsymbool van de stack
• 𝐹 ⊆ 𝑄 de verzameling final states.
2.1 De transitiefunctie dichterbij bekeken
Reden waarom z nodig is
1
, 2.2 Voorbeeld
𝐿 = {𝑎𝑛 𝑏𝑛 |𝑛 ≥ 0}
3 Instantaneous description
Definitie:
Het drie-tuple (q,w,u) met
• Q de huidige state van de accepter
• W het nog niet verwerkte deel van de invoerstring
• U de inhoud van de stack (met het meest linkse symbool van u TOS)
Noemen we de instantaneous description (ID) van een pushdown automaat.
Voorbeeld:
4 Taal geaccepteerd door een pushdown automaat
Definitie:
Stel 𝑀 = (𝑄, Σ, Γ, δ, 𝑞0 , 𝑧, 𝐹) een npda. De taal geaccepteerd door
M is de verzameling
𝐿(𝑀) = {𝑤 ∈ Σ∗ : (𝑞0 , 𝑤, 𝑧) ⊢ ∗𝑀 (𝑝, 𝜆, 𝑢), 𝑝 ∈ 𝐹, 𝑢 ∈ Γ ∗ }
Voorbeeld:
2
1 Automaten voor context-vrije talen
Voorbeelden:
𝐿 = {𝑎𝑛 𝑏𝑛 |𝑛 ≥ 0} → eindig geheugen is niet geschikt om bij te houden hoe veel a’s er tot nu toe
verwerkt zijn en dan even veel b’s toe te voegen.
𝐿 = {𝑤𝑤 𝑅 |𝑤 ∈ {𝑎, 𝑏}} → we hebben de mogelijkheid nodig om de sequentie karakters op te slaan
en in omgekeerde volgorde opnieuw te overlopen
Het idee:
Voeg een stack (vorm van geheugen) toe aan de
automaten die we tot nu toe gebruikt hebben
2 Nondeterministic pushdown
accepter (npda)
Definitie:
Een niet-deterministische pushdown accepter (npda)
wordt gedefinieerd door het tuple 𝑀 =
(𝑄, Σ, Γ, δ, 𝑞0 , 𝑧, 𝐹). Hierbij is
• Q een eindige verzameling interne toestanden (states) van de accepter.
• sigma het alfabet
• gamma een eindige verzameling symbolen die we het stack alfabet noemen
• 𝛿: 𝑄 × (Σ ∪ {𝜆}) × Γ → 𝑒𝑖𝑛𝑑𝑖𝑔𝑒 𝑑𝑒𝑒𝑙𝑣𝑒𝑟𝑧𝑎𝑚𝑒𝑙𝑖𝑛𝑔 𝑣𝑎𝑛 𝑄 × Γ ∗ de transitiefunctie
• 𝑞0 ∈ 𝑄 de initiële staat van de accepter
• 𝑧 ∈ Γ het startsymbool van de stack
• 𝐹 ⊆ 𝑄 de verzameling final states.
2.1 De transitiefunctie dichterbij bekeken
Reden waarom z nodig is
1
, 2.2 Voorbeeld
𝐿 = {𝑎𝑛 𝑏𝑛 |𝑛 ≥ 0}
3 Instantaneous description
Definitie:
Het drie-tuple (q,w,u) met
• Q de huidige state van de accepter
• W het nog niet verwerkte deel van de invoerstring
• U de inhoud van de stack (met het meest linkse symbool van u TOS)
Noemen we de instantaneous description (ID) van een pushdown automaat.
Voorbeeld:
4 Taal geaccepteerd door een pushdown automaat
Definitie:
Stel 𝑀 = (𝑄, Σ, Γ, δ, 𝑞0 , 𝑧, 𝐹) een npda. De taal geaccepteerd door
M is de verzameling
𝐿(𝑀) = {𝑤 ∈ Σ∗ : (𝑞0 , 𝑤, 𝑧) ⊢ ∗𝑀 (𝑝, 𝜆, 𝑢), 𝑝 ∈ 𝐹, 𝑢 ∈ Γ ∗ }
Voorbeeld:
2
