\( {L}_{1}=\left\{ { {(uw)}^{x}{w}^{y}{w}^{y} }|{ x,y > 0 } \right\} \)
\( {L}_{2}=\left\{ { {0}^{z}{1}^{2z} }|{ z> 0, \quad Wörtlänge \quad ist \quad immer \quad gerade } \right\} \)
Ich glaube beide Sprachen sind kontextfrei. Liege ich richtig?
Zu \( {L}_{1}\))
Das \( {L}_{1}\) nicht in REG liegt, kann man mit dem Pumping-Lemma zeigen. Aber \( {L}_{1}\) liegt in CF wie man mit einem PDA zeigen kann. S ist das Kellersymbol:
\( {z}_{0}uS -> {z}_{1}S \)
| \( {z}_{1}wS -> {z}_{0}S \)
| \( {z}_{1}wS -> {z}_{2}S \)
|
\( {z}_{2}wS -> {z}_{4}QS \)
| \( {z}_{2}wS -> {z}_{3}QS \)
| \( {z}_{3}wQ -> {z}_{3}QQ \)
|
\( {z}_{3}wQ -> {z}_{4}QQ \)
| \( {z}_{4}wQ -> {z}_{4}λ \)
| \( {z}_{4}λS -> {z}_{e}λ \)
|
Zu \( {L}_{2}\))
Das \( {L}_{2}\) nicht in REG liegt, kann man auch mit dem Pumping-Lemma zeigen. Aber dass \( {L}_{2}\) in CF liegt, da bin ich mir unsicherer. Wieder ein PDA:
\( {z}_{0}0S -> {z}_{1}QQS \)
| \( {z}_{0}0Q -> {z}_{1}QQQ \)
| \( {z}_{1}0Q -> {z}_{0}QQQ \)
|
\( {z}_{1}0Q -> {z}_{2}QQQ \)
| \( {z}_{2}1Q -> {z}_{2}λ\)
| \( {z}_{2}λS -> {z}_{e}λ\)
|
Sind meine Lösungen korrekt?
