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
!! 17.06.2018 (Jel.) Khanova škola zve nadšence ke spolupráci na překladech návodů pro učitele a rodiče.
! 04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17.01.2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17.01.2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
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

#1 18. 10. 2018 20:39

Zakara
Příspěvky: 41
Reputace:   
 

Jak sestavit k příkladu L1={w; w in {0,1}*... Konečný automat?

Dobrý den, prosím Vás o radu, jakym postupem řešit tenhle konečný automat?
L1 = {w; w in {0,1}*, w obsahuje lichý počet symbolů 0 a zároveň sudý (i nulový)  počet symbolů 1}

je posloupnost 011,00111,0001111... atd?

jestli ano, je možné k tomuto sestavit tenhle konečný automat na obrázku?
http://forum.matematika.cz/upload3/img/2018-10/87836_konecnyautomat1.png

Děkuji a přeji hezký den.

Offline

 

#2 18. 10. 2018 22:13

Davisek
Příspěvky: 40
Reputace:   
 

Re: Jak sestavit k příkladu L1={w; w in {0,1}*... Konečný automat?

↑ Zakara:

Mezi řetězce, které patří do L1 jsou napr, 0, 01100, 111101001, ...

Jednoduše jde vidět že automat přijme řetězec "00" , přitom tento řetězec nepatří do L1.
Takže odpověď je NE.

Obecný postup

Můžeme pokusit najít protipříklad. Ale ne vždy ho dokažeme najít. Třeba z důvodu, že automat vážně popisuje předepsaný jazyk.

Další možnost je se podívat na automat, a odhadnout jaký jazyk popisuje. Existuje k tomu algoritmus, který dokaže převést automat na regulární výraz. V našem případě automat popisuje regularní výraz  $r = (0^*11)^*$, který říká, že po libovolném počtu 0 nasleduje 11. Což rozhodně není L1

U složitých můžeme postupovat například takhle za předpokladu, že automat na obrazku je deterministicky, lze ho minimalizovat pokud už není. Tak můžeme sami vytvřoit minimální deterministicky automat, který bude popisovat předepsaný jazyk. Pokud ty dva automaty budou ekvivalentní tak, odpoveď je ano

Protože je známo, že existuje pouze JEDEN minimalní automat, který popisuje daný jazyk.
https://en.wikipedia.org/wiki/DFA_minimization

pozn. minimalním mýslím automat, z minimalním počtem stavů.

Offline

 

#3 19. 10. 2018 10:47 — Editoval Zakara (19. 10. 2018 11:06)

Zakara
Příspěvky: 41
Reputace:   
 

Re: Jak sestavit k příkladu L1={w; w in {0,1}*... Konečný automat?

↑ Davisek: Děkuji za odpověď, takže jak postupovat, abych z příkladu vydedukoval správný automat?

Offline

 

#4 19. 10. 2018 12:42

Davisek
Příspěvky: 40
Reputace:   
 

Re: Jak sestavit k příkladu L1={w; w in {0,1}*... Konečný automat?

↑ Zakara:

Na to je složítá odpověď. Například odpovědět otázka, jak postupovato obecně k dokázaní nějaké věty. Neexistuje. Je to tvůrčí činnost.
Samozřejmě existuje opět algoritmus který převede regulární výraz na nedeterministkcký konečný automat. Ale my nemáme ani ten regulární výraz, můžem ho vytvořit, ale je to zbytečně komplikované.

Pokud umíš, nakreslit automat, který přijimá jednodušší jazyk např. jazyk obsahující řetězce, které mají jen sudou délku, atd. tak umíš i tento, jen je to trošku komplikovanější.

-------------------

Jak bych asi postupoval já. Musíme si pamatovat 4 možnosti:
- počet 0 a 1 je sudý
- počet 0 je sudý a počet 1 je lichý
- počet 0 je lichý a počet 1 je sudý
- počet 0 a 1 lichý

To máme 4 stavy. Mezi jednotlivými stavy budeme různě přecházet podle 1 a 0. Jaky stav bude počáteční a jaký koncový nechám na tobě.

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson