Matematické Fórum

Zravim vsechny,
potreboval bych pomoct s pochopenim algoritmu A->a|BB, B->AB|b  bezkontextove gramatiky.
Nize uvadim jeho strucny popis a muj nahled na vec.

Mame bezkontextovou gramatiku, ktera ma pravidla  A->a|BB,  B->AB|b.
Aplikujeme tento algoritmus na automat v prave polovine obrazku.

Zadne nove stavy nejsou pridany, vsechny pridane prechody jsou oznaceny  promennymi.
Algoritmus prida prechody (q0,A,q1),(q1,B,q2) a (q2,A,q1) protoze  A->a, B->b.
Zduvodu B->AB, ted dostaneme (q0,B,q2) a (q2,B,q2) coz nam umoznuje pouzivat A->BB to nam prida (q0,A,q2),(q1,A,q2) a (q2,A,q2).



Co vlasne dela algoritmus A->a|BB,  B->AB|b ?

Podle me umoznil automatu v pravo prijimat vsechna slova w jazyka L kde L={w-je podmnozinou {a,b}*}
Kdezto automat v levo prijima pouze slova w kde L={w-je podmnozinou {a,b}*| w-zacina znakem "a" a konci znakem "b" a pocet obou znaku v prijatem slovu je shodny}.

V cem je vyhodny zmineny algoritmus? Mohl by me to nekdo osvetlit na nejakem jednoduchem prikladu?

V nasledujicim odkazu v sekci 3 je vse  popsano v originale:  www7.in.tum.de/um/bibdb/esparza/ufpcfg.pdf
Dekuji za odpoved