Question 5117 – UGC NET CS 2018 JUNE Paper-2
November 30, 2023Question 4888 – UGC NET CS 2018-DEC Paper-2
November 30, 2023Question 4887 – UGC NET CS 2018-DEC Paper-2
Consider the following language:
L 1 = { a n+m b n a m | n, m ≥ 0 }
L 2 = { a n+m b n+m a n+m |n, m ≥ 0 }
Which one of the following is correct?
Correct Answer: A
Question 20 Explanation:
→ L 1 is Context Free language because we can push all the a’s that come as input and when b’s come as input pop “n” number of a’s for “n” b’s from top of the stack and when again a’s come as input pop-up all the remaining a’s(i.e. “M” number of a’s) from top of the stack for “m” number of a’s coming as input.
Since we can have a pushdown automata for L 1 so we can say L 1 is a CFL.
→ L 2 is not a context free language because L is equivalent to language= {a p b p a p | p ≥ 0 }.
So for every “b” we can POP a’s came before “b” but for “a” which came after “b” we have nothing to POP on the top of stack. Since we can’t have a pushdown automata that can accept L 2 .
L 2 is not a CFL.
Since we can have a pushdown automata for L 1 so we can say L 1 is a CFL.
→ L 2 is not a context free language because L is equivalent to language= {a p b p a p | p ≥ 0 }.
So for every “b” we can POP a’s came before “b” but for “a” which came after “b” we have nothing to POP on the top of stack. Since we can’t have a pushdown automata that can accept L 2 .
L 2 is not a CFL.
Only L 1 is Context Free Language
Both L 1 and L 2 are not Context Free Language
Only L 1 is Context Free Language
Both L 1 and L 2 are Context Free Language
Subscribe
Login
0 Comments