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 L*2* 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:

- Given L1 is a context free language and L2 as a regular language then L1-L2 is context free language and
- ~L1(complement of context free) is not context free because context free is not closed under complement.
- Complement of regular language i.e. ~L2 is also regular ( so d is correct ) since statements a and c are false.

Hence,Option (C) is correct.

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.

Let's examine:

L1 ∩ L2 = { a^{i}b^{i}c^{i} , 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 ∪ ∅ = M^{c}.

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 L^{c} = Σ* and M^{c} ∪ Σ* = Σ* 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.

Hence, D is the correct option.

QUESTION: 10

Let L_{1} be a regular language L_{2}, be a deterministic context-free language and L_{3} 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.

### Identify Sets (Part-2)

Video | 00:18 min

### Identify Sets (Part-3)

Video | 00:22 min

### Identify Sets (Part-1)

Video | 00:18 min

### Identify Sets (Part-2) - Solution

Video | 00:34 min

- Test: Identify Class Language
Test | 10 questions | 20 min

- Test: Identify Class Language
Test | 15 questions | 45 min

- Identify Personalities
Test | 20 questions | 10 min

- Identify Personalities - 3
Test | 20 questions | 10 min

- Identify Personalities - 2
Test | 20 questions | 10 min