Test: Identify Class Language


10 Questions MCQ Test Mock Test Series - Computer Science Engg. (CSE) GATE 2020 | Test: Identify Class Language


Description
This mock test of Test: Identify Class Language for GATE helps you for every GATE entrance exam. This contains 10 Multiple Choice Questions for GATE Test: Identify Class Language (mcq) to study with solutions a complete question bank. The solved questions answers in this Test: Identify Class Language quiz give you a good mix of easy questions and tough questions. GATE students definitely take this Test: Identify Class Language exercise for a better result in the exam. You can find other Test: Identify Class Language extra questions, long questions & short questions for GATE on EduRev as well by searching above.
QUESTION: 1

Over the alphabet , {0,1} consider the language

Which of the following is true about L.

Solution:

L is regular.

QUESTION: 2

If L1 is context free language and L2 is a regular language which of the following is/are false?
a) L1-L2 is not context free
b) L1 ∩ L2 is context free
c) ~L1 is context free
d) ~L2 is regular

Solution:
QUESTION: 3

Let  denote the languages generated by the grammar S→ 0S0 I 00.

Which of the following is TRUE?

Solution:

Language generated by this grammar is L = (00)^+ that is regular but not 0^+

QUESTION: 4

The language accepted by a Pushdown Automaton in which the stack is limited to 10 items is best described as

Solution:

With only finite positions in stack, we can have only finite configurations and these can also be modeled as states in a finite
automata.

QUESTION: 5

The language 

Solution:

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]

Note :1. state changes make sure b's comes after a and c's comes after b's]

 

QUESTION: 6

Consider the languages:

 and

Which one of the following statements is FALSE?

Solution:

L1 is CFL [ put a's in stack , and pop a with each b]]
L2 is CFL [put b's in stack and pop b with each c ]
c) is True.

b) is True CFL is closed under Union [ S-> S1 | S2 where S1 is grammar for L1 and S2 for L2]
CFL is not closed under Intersection, so intersection of two CFLs may or may not be CFL. Lets examine:

L1 ∩ L2 = { aibici , i>0 } which is Context sensitive but not context free [can't match a's,b's and c's with one stack]
So a) is False

d) is True

QUESTION: 7

Let L be a regular language and M be a context-free language, both over the alphabet    denote the complements of  L and M respectively. Which of the following statements about the language 

Solution:

Take L = Σ* then Lc = ∅ and Mc ∪ ∅ = Mc.

We know that complement of CFL need not be a CFL as CFL is not closed under complement

So, (A) and (B) are false.

If we take L = ∅ then Lc = Σ* and Mc ∪ Σ* = Σ* which is regular - (C) is also false.

So, answer (D)

QUESTION: 8

The language  

Solution:

Regular (in fact finite). Since n is finite, we have a finite set of strings satisfying the given conditions. So, we can easily
make a finite automata for those strings.

QUESTION: 9

For     denote the decimal value of     

Which one of the following statements is true?

Solution:

L1 = { s∈(0+1)* ∣ d(s) mod 5=2 } is regular

having 2 as final state out of {0,1,2,3,4} states
as given in example in posted link [in same DFA , final state will be 2 instead of 0 ]

similarly L2 = { s∈(0+1)* ∣ d(s) mod 7≠4 } is also regular
having states {0,1,2,3,4,5,6} and all are final state except 4
L1 ∩ L2 is L (given problem ) is also regular
As regular languages are closed under intersection. D is correct option.

QUESTION: 10

Let L1 be a regular language L2,  be a deterministic context-free language and L3 a  recursively enumerable, but not recursive, language. Which one of the following statements is false?

Solution:

A) True : DCFL are closed under Intersection with Regular Languages
C) True : L1 is regular hence also CFL and every DCFL is also CFL and All CFL are closed under Union.
D) True : L1 is regular hence also RE; L2 is DCFL hence also RE; RE languages are closed under Intersection
B) False : L1 is recursive hence also decidable, L3 is RE but not Recursive hence it is undecidable. Intersection of Recursive
language and Recursive Enumerable language is Recursive Enumerable language.

Similar Content

Related tests