Matematické Fórum

komornik · 18. 11. 2011 18:31

Dobrý den
mam gramatiku S->S0|B1
B->C1|B
C->10
A mám vytvořit konečný nedeterministikcý automat.
Podle mně jde o gramatiku typu 3 levá.
Ale gramatiku G3L nevim jak nakreslit jako KA.
Předem děkuji za odpovědi.

radekm · 18. 11. 2011 20:39

Předpokládám, že pravou lineární gramatiku převést umíte. Otočením pravé strany pravidel dostaneme pravou lineární gramatiku pro jazyk se slovy pozpátku (rozmyslete si proč). A dál už je to jednoduché.

komornik · 19. 11. 2011 09:44

↑ radekm:
dostanu gramatiku :
S->0S|1B
B->1C|B
C->01

A otocenim prave strany pravidel mam gramatiku typu 3,ktera generuje reverzni jazyk.
To znamena ze derivaci pro :
3GL dostanu S=>1B=>11C=>1101
3GP dostanu S=>B1=>C11=>1011.

Takze sestrojeni grafu prechodu NKA sestrojim z prehozenych pravidel??

radekm · 20. 11. 2011 09:48

↑ komornik:

Takze sestrojeni grafu prechodu NKA sestrojim z prehozenych pravidel??

Z přehozených pravidel se sestrojí automat pro reverzní jazyk. Abychom dostali automat pro původní jazyk, je třeba prohodit koncové stavy s počátečními a otočit přechody.

Matematické Fórum

#1 18. 11. 2011 18:31

Gramatika na NKA

#2 18. 11. 2011 20:39

Re: Gramatika na NKA

#3 19. 11. 2011 09:44

Re: Gramatika na NKA

#4 20. 11. 2011 09:48

Re: Gramatika na NKA

Zápatí