UGC NET CS 2018 JUNE Paper-2
November 30, 2023UGC NET CS 2018-DEC Paper-2
November 30, 2023UGC NET CS 2018-DEC Paper-2
| Question 20 |
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?
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?
| 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 |
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.
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.