Matematické Fórum

iPwn · 26. 01. 2011 15:36

Zdravím,

potřeboval bych poradit se sestrojením konečného automatu:

KA by měl akceptovat následující množinu R slov složených ze znaků x a y: R = {slovo obsahuje stejný počet znaků x jako y}

automat ale pravděpodobně sestrojit nejde, netuším ovšem proč.

Předem děkuji za odpověď

kosto · 27. 01. 2011 17:17

↑ iPwn:
Automat naozaj nejde zostrojiť. Vieme totiž, že jazyk

$L_1 = \{a^n b^n\ |\ n \in \mathbb{N}\}$

nie je regulárny (neexistuje konečný automat, ktorý ho akceptuje). To sa dá dokázať pomocou pumpovacej lemy pre regulárne jazyky (pre podrobnosti o pumpovacej leme viď tento odkaz), ale je to aj pomerne známy fakt sám o sebe.

Teraz, vieme, že regulárne jazyky sú uzavreté na prienik. Taktiež vieme, že jazyk

$L_2 = \{a^i b^j\ |\ i,j \in \mathbb{N}\}$

je regulárny - zostrojiť konečný automat nie je až také ťažké. Ale platí

$L_1 = L_2 \cap R$ ,

kde R je jazyk zo zadania. Jazyk $L_2$ je regulárny, čo znamená, že keby bol R regulárny, z uzavretosti na prienik by vyplývalo, že je regulárny aj jazyk $L_1$ , čo ale nie je. Preto jazyk R nie je regulárny .

kosto · 27. 01. 2011 17:25

↑ kosto:
Akosi automaticky som x,y zamenil za a,b (konvencia). Dufam, ze som velmi nezmiatol.

iPwn · 27. 01. 2011 18:00

V pořádku, je to srozumitelné. Děkuji za odpověď :)

Matematické Fórum

#1 26. 01. 2011 15:36

Sestavení konečného automatu

#2 27. 01. 2011 17:17

Re: Sestavení konečného automatu

#3 27. 01. 2011 17:25

Re: Sestavení konečného automatu

#4 27. 01. 2011 18:00

Re: Sestavení konečného automatu

Zápatí