...
Question 6720 – Theory-of-Computation
March 1, 2024
UGC NET CS 2015 Dec – paper-3
March 1, 2024
Question 6720 – Theory-of-Computation
March 1, 2024
UGC NET CS 2015 Dec – paper-3
March 1, 2024

Question 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

{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
(a)-(i), (b)-(ii), (c)-(iii), (d)-(iv)
B
(a)-(i), (b)-(ii), (c)-(iv), (d)-(iii)
C
(a)-(iv), (b)-(iii), (c)-(ii), (d)-(i)
D
(a)-(iv), (b)-(iii), (c)-(i), (d)-(ii)
0 0 votes
Article Rating
Subscribe
Notify of
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x
error: Alert: Content selection is disabled!!