+1 Daumen
955 Aufrufe

\( {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?

Avatar von

L_(2) "Wortlänge immer gerade". Ist das eine Vorgabe in der Definition von L_(2)?

Bedingt das nicht, dass z selbst gerade ist?

Insgesamt muss das Wort gerade sein, also muss auch z gerade sein. Habe ich auch so verstanden. Also es gibt eine gerade Anzahl an 0en und doppelt so viele 1en. Quasi \({0}^{2z}{1}^{4z}\) für z>0.

Quasi: …

Ja. So lese ich das zumindest.

1 Antwort

+1 Daumen
 
Beste Antwort

\(L_1\) ist regulär. Wörter aus \(L_1\) bestehen aus einer beliebigen Anzahl von abwechselnd u und w, gefolgt von einer geraden Anzahl von w.

\(L_2\) ist nicht regulär wegen Pumping-Lemma.

\(L_2\) ist kontextfrei wegen folgender Grammatik:

  • S → 00P1111
  • P → 00P1111
  • P → ε
Avatar von 5,6 k

Ah, vielen Dank. Jetzt habe ich gemerkt, dass man aus L1 auch einen DFA/NFA machen kann.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community