Identify-Class-Language

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?

A
Push Down Automate (PDA) can be used to recognize L1 and L2
B
L1 is a regular language
C
All the three languages are context free
D
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

A
Not recursive
B
Regular
C
Context free but not regular
D
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} ?

A
It is not accepted by a Turing Machine
B
It is regular but not context-free
C
It is context-free but not regular
D
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: 

A
not recursive.
B
is recursive and is a deterministic CFL.
C
is a regular language.
D
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

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access