Linker-Loader
October 10, 2023Algorithms
October 11, 2023Theory-of-Computation
| Question 3 |
Which one of the following strings is not a member of L(M)?
Let M = (K,Σ,Γ,Δ,s,F) be a pushdown automaton, where
K = {s,f}, F = {f}, Σ = {a,b}, Γ = {a} and
Δ = {((s,a,ε), (s,a)), ((s,b,ε), (s,a)), ((s,a,ε), (f,ε)), ((f,a,a), (f,ε)), ((f,b,a), (f,ε))}
| aaa | |
| aabab | |
| baaba | |
| bab |
Question 3 Explanation:
First let’s draw PDA,
Now, here transition ((s,a,t), (s,a)) implies reading input symbol ‘a’ in the state ‘s’ we have to move ‘s’ having any symbol on the top of stack … epsilon here implies “anything on of Top of stack”.
Now, observe the PDA carefully, it is saying that in the starting you have to push one ‘a’ for each of ‘a’ and ‘b’. And in the end you have to pop one ‘a’ by one ‘a’ by one ‘a’ or one ‘b’. Thus the count of a’s and b’s in first half of the string should be equal to second half of string. Now to move from first half to second half we are required one ‘a’, i.e., moving from s to f.
So, all odd strings in which ‘a’ is the middle element will be accepted.
Thus in our question, option (B) is aabab having ‘b’ in the middle and thus can’t be accepted.
Now, here transition ((s,a,t), (s,a)) implies reading input symbol ‘a’ in the state ‘s’ we have to move ‘s’ having any symbol on the top of stack … epsilon here implies “anything on of Top of stack”.
Now, observe the PDA carefully, it is saying that in the starting you have to push one ‘a’ for each of ‘a’ and ‘b’. And in the end you have to pop one ‘a’ by one ‘a’ by one ‘a’ or one ‘b’. Thus the count of a’s and b’s in first half of the string should be equal to second half of string. Now to move from first half to second half we are required one ‘a’, i.e., moving from s to f.
So, all odd strings in which ‘a’ is the middle element will be accepted.
Thus in our question, option (B) is aabab having ‘b’ in the middle and thus can’t be accepted.
Correct Answer: B
Question 3 Explanation:
First let’s draw PDA,
Now, here transition ((s,a,t), (s,a)) implies reading input symbol ‘a’ in the state ‘s’ we have to move ‘s’ having any symbol on the top of stack … epsilon here implies “anything on of Top of stack”.
Now, observe the PDA carefully, it is saying that in the starting you have to push one ‘a’ for each of ‘a’ and ‘b’. And in the end you have to pop one ‘a’ by one ‘a’ by one ‘a’ or one ‘b’. Thus the count of a’s and b’s in first half of the string should be equal to second half of string. Now to move from first half to second half we are required one ‘a’, i.e., moving from s to f.
So, all odd strings in which ‘a’ is the middle element will be accepted.
Thus in our question, option (B) is aabab having ‘b’ in the middle and thus can’t be accepted.
Now, here transition ((s,a,t), (s,a)) implies reading input symbol ‘a’ in the state ‘s’ we have to move ‘s’ having any symbol on the top of stack … epsilon here implies “anything on of Top of stack”.
Now, observe the PDA carefully, it is saying that in the starting you have to push one ‘a’ for each of ‘a’ and ‘b’. And in the end you have to pop one ‘a’ by one ‘a’ by one ‘a’ or one ‘b’. Thus the count of a’s and b’s in first half of the string should be equal to second half of string. Now to move from first half to second half we are required one ‘a’, i.e., moving from s to f.
So, all odd strings in which ‘a’ is the middle element will be accepted.
Thus in our question, option (B) is aabab having ‘b’ in the middle and thus can’t be accepted.
Subscribe
Login
0 Comments