[Gramatyki] Automat ze stosem

[lolomak]

Witam mam problem z jednym zadaniem z automatow bylbym bardzo wdzieczny gdyby ktos mi pomogl

Skonstruuj automat ze stosem oraz gramatyke bez kontekstowa dla jezyka slow nad alfabetem \(\displaystyle{ \left\{ 0,1\right\}}\)ktory zaczyna i konczy sie tym samym symbolem i posiada taka sama liczbe \(\displaystyle{ 0}\) i \(\displaystyle{ 1}\)


Z gory dziekuje za pomoc

[lolomak]

up

[Afish]

Gramatyka:
\(\displaystyle{ S \rightarrow \epsilon | 0A1A1A0 | 1A0A0A1 \\
A \rightarrow 0A1 | 1A0 | 01A | 10A | \epsilon}\)
Najpierw \(\displaystyle{ S}\) obsługuje przypadek skrajny, potem robię słowo zaczynające się i kończące zerem (jedynką) i mające dwie odpowiadające jedynki (zera).
\(\displaystyle{ A}\) odpowiada za wstawienie dowolnej liczby sparowanych zer i jedynek.

[norwimaj]

Ja bym dla \(\displaystyle{ A}\) dał takie reguły:
\(\displaystyle{ A \rightarrow 0A1 | 1A0 | AA | \epsilon.}\)
Wówczas z gramatyki będzie można wyprowadzić nawet takie słowa, jak \(\displaystyle{ 0^51^301^40.}\)