,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.
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller GeniusGears. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $2.72. You're not tied to anything after your purchase.
