Home » Theory of Computation » Theory of computation miscellaneous » Question

Theory of computation miscellaneous

Theory of Computation

  1. The language { am bn cm + n | m , n > 1 } is
    1. regular
    2. context-free but not regular
    3. context-senstitive but not context-free
    4. type-0 but not context-sensitive
Correct Option: B

Language is not regular bcoz we need to match count of c's is equal to count of b's + count of a's and that can implement by PDA
∂(q0 , a ,^) = (q0 , a) [push a in stack, as per language a comes first]
∂(q0 , a , a) = (q0 , aa) [push all a's into stack]
∂(q0 , b , a) = (q1 , ba) [push b in stack, state change to q1 that sure b comes after a]
∂(q1 , b , b) = (q1 , bb) [push all b's in stack]
∂(q1 , c , b) = (q2 , ^) [pop one b for one c]
∂(q2 , c , b) = (q2 , c) [pop one b's for each c and continue same]
∂(q2 , c , a) = (q3 , ^) [pop one a for one c, when there is no more b in stack]
∂(q3 , c , a) = (q3 , ^) [pop one a for each c and continue same]
∂(q3 , ^ , ^) = (qf , ^) [if sum of c's is sum of a's and b's then stack will be empty when there is no c in input]
Hence, language is context- free but not regular.



Your comments will be displayed only after manual approval.