Matematické Fórum

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

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