Question 6720 – Theory-of-Computation
March 1, 2024UGC NET CS 2015 Dec – paper-3
March 1, 2024Question 6927 – Theory-of-Computation
Match the following:
Correct Answer: C
Question 514 Explanation:
{an bn|n > 0} is a deterministic context free language but not regular because the given language requires a storing device and finite state machine does not contain any storing device. {an bn|n > 0} can be accepted by a pushdown automata by pushing all the a’s on top of stack and when b’s come as input pop one “a” for each “b”.
The given language {an bn an. | n > 0} is a context sensitive language because for this language if we push a’s on top of stack and for every “b” we will pop a single “a” from top of stack and when after “b” again “a” will come as input then that time stack will be empty and we can’t compare number of a’s that come after “”b”. But we can have a linear bounded automata that can accept the given language by moving the read/write head accordingly.
Since the given language is CSL and CSL are closed under complement so given language can not be accepted by a deterministic pushdown automation
The given language {an bn an. | n > 0} is a context sensitive language because for this language if we push a’s on top of stack and for every “b” we will pop a single “a” from top of stack and when after “b” again “a” will come as input then that time stack will be empty and we can’t compare number of a’s that come after “”b”. But we can have a linear bounded automata that can accept the given language by moving the read/write head accordingly.
Since the given language is CSL and CSL are closed under complement so given language can not be accepted by a deterministic pushdown automation
{an bn an} is context sensitive language but not context free language, the logic is the same as above. SInce for given language can’t be accepted by pushdown automata, so it is not a context free language.
(a)-(i), (b)-(ii), (c)-(iii), (d)-(iv)
(a)-(i), (b)-(ii), (c)-(iv), (d)-(iii)
(a)-(iv), (b)-(iii), (c)-(ii), (d)-(i)
(a)-(iv), (b)-(iii), (c)-(i), (d)-(ii)
Subscribe
Login
0 Comments