Matematické Fórum

lexa47 · 26. 04. 2010 12:06

Ahoj, pomohl by mi někdo začít s tímhle příkladem..

Dokažte, že následující bezkontextová gramatika generuje jazyk {w náleží {a, b}* | |w|a = |w|b}:
S −! epsilon | aB | bA
A −! aS | bAA
B −! bS | aBB
Nápoveda: Postupujte indukcí podle délky slov generovaných jednotlivými neterminály.

Kondr · 27. 04. 2010 08:18

Lemma
(1)Slova délky k generovaná neterminálem S tvoří množinu všech slov délky k, pro které $|w|_a=|w|_b$ .
(2)Slova délky k generovaná neterminálem A tvoří množinu všech slov délky k, pro které $|w|_a=|w|_b+1$ .
(3)Slova délky k generovaná neterminálem B tvoří množinu všech slov délky k, pro které $|w|_b=|w|_a+1$ .

Důkaz
Dokazujeme všechny části souběžně a to indukcí podle $k$ .

Bázový krok: pro délku 0 generuje S epsilon, A,B negenerují nic. Pro délku negeneruje S nic, A,B generují po řadě a,b. To sedí.

Indukční krok: (věříme tomu pro k=n a dokazujeme pro k=n+1)
Množinu všech slov délky n+1, která splňují $|w|_a=|w|_b$ lze rozdělit podle toho, jestli začínají na a nebo b. Ty, co začínají na a musí pokračovat řetězcem $w'$ délky n splňujícím $|w'|_a+1=|w'|_b$ . Ten je z indukčního předpokladu generován neterminálem B. Na druhou stranu každé slovo generované B po připojení a na začátek vytvoří slovo, které splňuje $|w|_a=|w|_b$ . Analogicky slovo začínající b-čkem splní $|w|_a=|w|_b$ právě když je za tím b-čkem slovo generované A. Slova nenulové délky $n+1$ splňující $|w|_a=|w|_b$ lze proto generovat vždy buď jako $bA$ nebo $aB$ ,
přesně tato slova generuje $S$ .

Zbývá rozmyslet indukční krok pro (2) a (3), opět se bude operovat s tím, jestli slovo začíná na a nebo b ...

Protože jsme dokázali naše lemma pro všechna k, platí i zadané tvrzení.

Zdenek01 · 27. 04. 2010 17:34

Mohl by někdo prosím vysvětlit indukční krok pro tu (2)? Absolutně jsem se zatím nechyt. Předpokládám, že ten krok (3) bude podobný (skoro totožný) s krokem (2).

Zdenek01 · 28. 04. 2010 07:05

Prosím Vás můžete mi ukázat i ten indukční krok 2 opravdu si stím nevím rady (vždy když se jedná o dokazování tak jsem ztracen). Nutně potřebuju tento příklad vyřešit a vůbec stím nemohu hnout. Předem děkuji za pomoc

Kondr · 28. 04. 2010 10:57

No tak to bude dost podobný té (1), ne? Rozdělíme to na případy, kdy slovo začíná a-čkem a kdy začíná b-čkem. Pokud začíná a-čkem, musí následovat část slova délky n, která obsahuje stejně a-ček jako b-ček. To jsou právě ta slova délky n, která generuje neterminál S (dle indukčního předpokladu). Pokud začíná b-čkem, následuje slovo délky n, které má o dvě a-čka víc. My tvrdíme, že právě tato slova generuje dvojice netermiálů AA. Snadno vidíme, že když A generuje slova s jedním a-čkem navíc, bude AA generovat slova s dvěmi a-čky navíc. Zbývá ukázat, že každé slovo, které má dvě a-čka navíc lze generovat dvojicí neterminálů AA. Procházíme slovem od začátku do konce a sledujeme, jak se nám vyvíjí rozdíl počtu aktuálně načtených a-ček a b-ček. Na začátku je nula, na konci 2, mění se vždy o 1. Na nějaké pozici dosáhne hodnoty 1. Když na této pozici slovo rozdělíme na dvě části, dostaneme dvě slova, která jsou obě generovaná neterminálem A.

Zdenek01 · 28. 04. 2010 20:57

↑ Kondr:Děkuji za vysvětlení, jen se chci ještě zeptat, jestli by jste mi neukázal na nějakém příkladu to procházení slovem od začátku až do konce a sledování rozdílu a-ček a b-ček (na, které pozici dosáhne hodnoty 1, tak abych to mohl rozdělit)? Jinak indukční krok 2 dá se sním popsat i ten indukční krok č.3? Děkuji za odpovědi

Matematické Fórum

#1 26. 04. 2010 12:06

Bezkontextový jazyk, ověření

#2 27. 04. 2010 08:18

Re: Bezkontextový jazyk, ověření

#3 27. 04. 2010 17:34

Re: Bezkontextový jazyk, ověření

#4 28. 04. 2010 07:05

Re: Bezkontextový jazyk, ověření

#5 28. 04. 2010 10:57

Re: Bezkontextový jazyk, ověření

#6 28. 04. 2010 20:57

Re: Bezkontextový jazyk, ověření

Zápatí