Regulární jazyky Flashcards
(5 cards)
1
Q
Zobecněná přechodová funkce
A
Je funkce δ:Q×Σ→Q, která jendoznačně definuje následující stav po zpracování řetězce na vstupu z aktuálního stavu.
2
Q
Ekvivalentní rozpoznávací automaty
A
Jsou automaty, které akceptují stejný jazyk.
3
Q
Redukovaný rozpoznávací automat
A
Takový reprezentant třídy ekvivalentních automatů, který má minimální počet stavů
4
Q
Kdy můžu z gramatiky sestrojit konečný automat?
A
Pouze ke gramatikám typu G3P s pravidly
v regulárním tvaru X→aY nebo X→e , kde X,Y∈N a a∈T, kde navíc pro žádný neterminální symbol neexistuje více než jedno pravidlo se stejným terminálním symbolem na pravé straně
5
Q
Co znamená, když je gramatika G3P v regulárním tvaru?
A
Pravidla jsou ve tvaru X→aY nebo X→e , kde X,Y∈N a a∈T
