Question 1

Consider the languages L1,L2 and L3 as given below.

    L1 = {0p1q|p,q∈N},
    L2 = {0p1q|p,q∈N and p=q} and
    L3 = {0p1q0r|p,q,r∈N and p=q=r}.

Which of the following statements is NOT TRUE?

Push Down Automate (PDA) can be used to recognize L1 and L2
L1 is a regular language
All the three languages are context free
Turing machines can be used to recognize all the languages
       Theory-of-Computation       Identify-Class-Language       GATE 2011
Question 1 Explanation: 
L1: regular language
L2: context free language
L3: context sensitive language
Question 2

Let L = L1 ∩ L2, where L1 and L2 are languages as defined below:

    L1 = {ambmcanbn | m,n ≥ 0 }
    L2 = {aibjck | i,j,k ≥ 0 }

Then L is

Not recursive
Context free but not regular
Recursively enumerable but not context free
       Theory-of-Computation       Identify-Class-Language       GATE 2009
Question 2 Explanation: 
The strings in L1 are {c, abc, cab, abcab, aabbcab, abcaabb, aabbcaabb,.....} and the strings in L2 are {ϵ, a, b, c, ab, bc, ac, abc, aabc, abbc, abcc, aabbcc, …..}
Clearly, L1 ∩ L2 is {axbx | x ≥0}, which is CFL but not regular.
Question 3

Which of the following is true for the language {ap|p is a prime} ?

It is not accepted by a Turing Machine
It is regular but not context-free
It is context-free but not regular
It is neither regular nor context-free, but accepted by a Turing machine
       Theory-of-Computation       Identify-Class-Language       GATE 2008
Question 3 Explanation: 
Finding prime number cannot be done by FA or PDA, so it cannot be regular or CFL. This language can be recognized by LBA, hence it can be accepted by Turing Machine.
Question 4

The language L = {0i21i | i≥0} over the alphabet {0, 1, 2} is: 

not recursive.
is recursive and is a deterministic CFL.
is a regular language.
is not a deterministic CFL but a CFL.
       Theory-of-Computation       Identify-Class-Language       GATE 2007
Question 4 Explanation: 
We have to match number 0’s before 2 and number of 1’s after 2, both must be equal in order to string belongs to language. This can be done by deterministic PDA. First we have to push 0’s in stack, when “2” comes , ignore it and after for each 1’s we have to pop one “0” from stack. If stack and input string both are empty at the same time then the string will be accepted else rejected. NOTE: i>=0 , so a single “2” is also accepted by DPDA. Hence this language is DCFL and every DCFL is recursive also, so it is also a recursive language.
There are 4 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

Register Now

If you have registered and made your payment please contact to get access