Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

Stránky: 1

 

#1 18. 11. 2011 18:31

komornik
Zelenáč
Příspěvky: 17
Reputace:   0 
 

Gramatika na NKA

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.

Offline

 

#2 18. 11. 2011 20:39

radekm
Příspěvky: 146
Reputace:   11 
Web
 

Re: Gramatika na NKA

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é.

Offline

 

#3 19. 11. 2011 09:44

komornik
Zelenáč
Příspěvky: 17
Reputace:   0 
 

Re: Gramatika na NKA

↑ 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??

Offline

 

#4 20. 11. 2011 09:48

radekm
Příspěvky: 146
Reputace:   11 
Web
 

Re: Gramatika na NKA

↑ 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.

Offline

 

 

Stránky: 1

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson