Jak sestrojit konecny automat pro jazyk? – Offtopic – Fórum – Programujte.com

Ahojte,

cele odpoledne valcim se sestavenim konecneho automatu pro jazyk L=[(a+ba*)*(b+c)*(cc)*], ale nemuzu se pohnout s mista, jak to poskladat dohromady.

Nenasel by se nekdo, kdo by mi s timhle pomohl?
Dekuji

#1 Ales
můžeš použít metodu sousedů (je jednoduchá, ale trochu pracnější)

#2 crazy
Metodu sousedu? Muzes prosimte naznacit, jak funguje?

Už je asi pozdě, ale já bych to pravděpodobně udělal jednoduchým postupem, který zahrnuje více kroků. Já bych regulární výraz definující jazyk L=[(a+ba*)*(b+c)*(cc)*] rozdělil na tři části a pak zřetězil (nebo na více částí a sjednocoval, řetězil atd.). Konkrétně bych udělal KA pro (a+ba*)*, pro (b+c)*, a pro (cc)*, pak bych je přes epsilonové hrany zřetězil a mám požadovaný KA. V případě potřeby bych jej pak samozřejmě převedl na deterministický, úplný, minimalizovaný atd., ale na to už jsou "jednoduché" algoritmy - tzn. nemusíš přemýšlet :-D (téměř ;-) ).

Není to dokonalé, ale je to relativně jednoduché, jasné a funguje to. To by byl asi první postup, který by mě napadl, a který bych udělal. Pokud bych se tím chtěl více zabývat, hledal bych algoritmy a postupy, kterými se to dělá optimálně, ale jelikož se problematikou formálních jazyků zabývám jen v rámci studia (a zatím dál nemířím, přestože je to zajímavý obor), a předpokládám, že ty taktéž, tak tohle je, myslím, dostačující postup, který funguje a je relativně jednoduchý (i přestože zahrnuje více kroků).