,Question 1 [15]
Build a DPDA to show that the language L = {(ba)na(ab)n-2 |
n > 2} is deterministic context free.
To show that the language \( L = \{(ba)^n(ab)^{n-2} \,|\, n > 2\} \) is deterministic context-free, we can construct a
deterministic pushdown automaton (DPDA) that recognizes it.
Here's the high-level approach to construct the DPDA:
1. The DPDA will use the stack to keep track of the difference in occurrences of 'a' and 'b' between the two parts
of the string.
2. It will ensure that the number of 'b's before 'a' matches the number of 'a's after 'b', except for the first 'a' and la
two 'b's.
3. The DPDA will have a stack alphabet {A, B, Z}, where 'A' represents 'a', 'B' represents 'b', and 'Z' is the bottom
of the stack marker.
4. It will transition between states based on the input symbol and the top of the stack.
Here's the detailed construction of the DPDA:
1. Initial State:
- Start in state \( q_0 \) with \( Z \) on the stack.
2. Read 'b's:
- In state \( q_0 \), for each 'b' read, push \( B \) onto the stack.
3. Read 'a':
- Transition to state \( q_1 \) when reading the first 'a'.
- In state \( q_1 \), for each 'a' read, push \( A \) onto the stack.
4. Transition from \( q_1 \) to \( q_2 \):
- When encountering 'a' after the first one, replace \( A \) with \( \varepsilon \) (pop \( A \) from the stack) withou
consuming input.
- When encountering 'b', transition to state \( q_2 \) and push \( B \) onto the stack.
5. Transition from \( q_2 \) to \( q_3 \):
- Keep reading 'b's while popping \( B \) from the stack.
- When you encounter the second-to-last 'b', transition to state \( q_3 \).
6. Transition from \( q_3 \) to \( q_4 \):
- In state \( q_3 \), read the last 'b'.
- When encountering 'a', transition to state \( q_4 \) without consuming input.
7. Acceptance State \( q_4 \):
- In state \( q_4 \), accept if the input is empty and the stack contains only \( Z \), meaning all 'a's after the initia
'b's have been consumed.
8. Handling Invalid Input:
- If at any point the number of 'a's exceeds the number of 'b's (except for the last two 'b's), reject the input by
transitioning to a non-accepting state.
This DPDA will recognize the language \( L \) and thus demonstrates that \( L \) is deterministic context-free.
,Question 2 [15] Prove that the language L = {banb2nan+1 | n > 0} over the
alphabet Σ = {a, b} is non-context free. Use the pumping lemma with length.
To prove that the language \( L = \{ba^n b^{2n} a^{n+1} \,|\, n > 0\} \) is non-context free, we can use the pumping
lemma for context-free languages. The pumping lemma states that if \( L \) is a context-free language, then there
exists a constant \( p \) (the pumping length) such that any string \( s \) in \( L \) with length at least \( p \) can be
divided into five substrings \( uvwxy \) satisfying the following conditions:
1. For any \( i \geq 0 \), the string \( uv^iwx^iy \) is also in \( L \).
2. \( |vwx| \leq p \).
3. \( |vx| \geq 1 \).
Let's assume \( L \) is context-free and let \( p \) be the pumping length as per the pumping lemma.
Consider the string \( s = ba^p b^{2p} a^{p+1} \). Since \( |s| \geq p \), the pumping lemma guarantees that \( s \)
can be divided into five substrings \( uvwxy \) such that the conditions of the lemma hold.
Now, let's analyze the possible cases:
1. If \( vwx \) contains only \( b \)'s, pumping it will result in a string where the number of \( b \)'s is not twice the
number of \( a \)'s, violating the condition of the language.
2. If \( vwx \) contains both \( a \)'s and \( b \)'s, pumping it will result in a string where the number of \( a \)'s is no
longer one more than half the number of \( b \)'s, violating the condition of the language.
3. If \( vwx \) contains only \( a \)'s, pumping it will result in a string where the number of \( a \)'s after the initial
sequence of \( b \)'s is no longer one more than the number of \( b \)'s before that sequence, violating the conditio
of the language.
In each case, pumping \( uvwxy \) leads to a string that does not belong to \( L \). Therefore, our assumption that
L \) is context-free is incorrect, and \( L \) is non-context free.
Alle Vorteile der Zusammenfassungen von Stuvia auf einen Blick:
Garantiert gute Qualität durch Reviews
Stuvia Verkäufer haben mehr als 700.000 Zusammenfassungen beurteilt. Deshalb weißt du dass du das beste Dokument kaufst.
Schnell und einfach kaufen
Man bezahlt schnell und einfach mit iDeal, Kreditkarte oder Stuvia-Kredit für die Zusammenfassungen. Man braucht keine Mitgliedschaft.
Konzentration auf den Kern der Sache
Deine Mitstudenten schreiben die Zusammenfassungen. Deshalb enthalten die Zusammenfassungen immer aktuelle, zuverlässige und up-to-date Informationen. Damit kommst du schnell zum Kern der Sache.
Häufig gestellte Fragen
Was bekomme ich, wenn ich dieses Dokument kaufe?
Du erhältst eine PDF-Datei, die sofort nach dem Kauf verfügbar ist. Das gekaufte Dokument ist jederzeit, überall und unbegrenzt über dein Profil zugänglich.
Zufriedenheitsgarantie: Wie funktioniert das?
Unsere Zufriedenheitsgarantie sorgt dafür, dass du immer eine Lernunterlage findest, die zu dir passt. Du füllst ein Formular aus und unser Kundendienstteam kümmert sich um den Rest.
Wem kaufe ich diese Zusammenfassung ab?
Stuvia ist ein Marktplatz, du kaufst dieses Dokument also nicht von uns, sondern vom Verkäufer GeniusGears. Stuvia erleichtert die Zahlung an den Verkäufer.
Werde ich an ein Abonnement gebunden sein?
Nein, du kaufst diese Zusammenfassung nur für 2,65 €. Du bist nach deinem Kauf an nichts gebunden.
