COS3701
Assignment 2
DUE 27 June 2024
,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.
Assignment 2
DUE 27 June 2024
,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.
