BI-AAG.21 q04

[NEBODOVANÁ OTÁZKA]

Byl pro tebe náš cheatsheet alespoň jednou užitečný?

• Ano

• Ne

[NEBODOVANÁ OTÁZKA]

Rozumím algoritmu pro odstranění ε-přechodů z NKA

• Ano

• Ne

Který z následujících formalismů dokáže popsat největší množinu jazyků?

• Deterministický konečný automat (DKA)

• Nedeterministický konečný automat (NKA) s ε-přechody

• Bezkontextová gramatika (BG)

• Všechny ostatní možnosti jsou špatně

V čem se liší definice DKA a NKA?

• Množina stavů

• Vstupní abeceda

• Přechodová funkce

• Počáteční stav(y)

• Množina koncových stavů

V čem se liší definice NKA a NKA s ε-přechody?

• Množina stavů

• Vstupní abeceda

• Přechodová funkce

• Počáteční stav(y)

• Množina koncových stavů

Nechť L je konečný jazyk. L je určitě:

• Regulární jazyk

• Bezkontextový jazyk

• Kontextový jazyk

• Rekurzivně spočetný jazyk

• Nekonečný jazyk :-)

[čtěte pozorně]

Která tvrzení o stavech ze zadaného automatu jsou pravdivá?

• q0 je užitečný stav

• q1 je zbytečný stav

• q2 je užitečný stav

• q2 je dosažitelný stav