2022 AFJ Cvičenie č. 7 - Zásobníkové automaty

Zhrnutie prednášky

Cvičenie nadväzuje na prednášku o zásobníkových automatoch, ktoré akceptujú bezkontextové jazyky. Na učebnicovom jazyku {aⁿbⁿ | n ≥ 0} sa ukazuje, prečo ho konečný automat nerozpozná: má obmedzený počet stavov, a preto nevie počítať neohraničený počet symbolov, zatiaľ čo zásobník poskytuje teoreticky nekonečnú pamäť. Návrh automatu má dve fázy: v stave q0 sa každé prečítané a ukladá do zásobníka nad počiatočný symbol Z0. Po prvom b automat prejde do stavu q1, kde páruje každé b na vstupe s jedným a vo zásobníku, ktoré vyberie. Ak sa po spracovaní vstupu objaví na vrchu zásobníka opäť Z0, automat prejde do akceptačného stavu q2.

• - Jazyk aⁿbⁿ je bezkontextový, ale nie regulárny.
• - Konečný automat nevie počítať neohraničený počet symbolov, zásobník má teoreticky nekonečnú pamäť.
• - Návrh zásobníkového automatu je ako písanie programu: treba vymyslieť, ako sa použije zásobník.
• - Fáza 1 (q0): každé prečítané a sa vloží do zásobníka.
• - Fáza 2 (q1): každé b sa spáruje s jedným a, ktoré sa zo zásobníka odstráni.
• - Ak sa na vrchu zásobníka objaví Z0, automat prejde do akceptačného stavu q2.

Zhrnutie pripravené s pomocou AI z prepisu videa.