# Formal Language & Automata Theory

40 Questions | Total Attempts: 378  Settings  .

• 1.
Let S and T be language over ={a,b} represented by the regular expressions (a+b*)* and (a+b)*, respectively. Which of the following is true?
• A.

ScT (S is a subset of T)

• B.

TcS (T is a subset of S)

• C.

S=T

• D.

SnT=Ø

• 2.
Let L denotes the language generated by the grammar S – OSO/00. Which of the following is true?
• A.

L = O

• B.

L is regular but not O

• C.

L is context free but not regular

• D.

L is not context free

• 3.
Consider the following two statements:S1: { 0^2n |n >= l} is a regu1ar languageS2: { 0^m 0^n 0^(m+n) l m >= 1 and n >= 2} is a regu1ar languageWhich of the following statements is correct?
• A.

Only S1 is correct

• B.

Only S2 is correct

• C.

Both S1 and S2 are correct

• D.

None of S1 and S2 is correct

• 4.
Which of the following statements in true?
• A.

If a language is context free it can always be accepted by a deterministic push-down automaton

• B.

The union of two context free languages is context free

• C.

The intersection of two context free languages is context free

• D.

The complement of a context free language is context free

• 5.
Given an arbitrary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least.
• A.

N^2

• B.

2^N

• C.

2N

• D.

N!

• 6.
Let L={w  (0 + 1)*|w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?
• A.

(0*10*1)*

• B.

0*(10*10*)*

• C.

0*(10*1*)*0*

• D.

0*1(10*1)*10*

• 7.
Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?
• A.

L2 – L1 is recursively enumerable.

• B.

L1 – L3 is recursively enumberable

• C.

L2 \cap L1 is recursively enumberable

• D.

L2 \cup L1 is recursively enumberable

• 8.
Consider the languages L1={|i != j}, L2={|i = j}, L3 = {|i = 2j+1}, L4 = {|i != 2j}. Which one of the following statements is true?
• A.

Only L2 is context free

• B.

Only L2 and L3 are context free

• C.

Only L1 and L2 are context free

• D.

All are context free

• 9.
Let w be any string of length n is {0,1}*. Let L be the set of all substrings of w. What is the minimum number of states in a non-deterministic finite automaton that accepts L?
• A.

n-1

• B.

N

• C.

N+1

• D.

2n-1

• 10.
Given the language L = {ab, aa, baa}, whih of the following strings are in L*?….1) abaabaaabaa….2) aaaabaaaa….3) baaaaabaaaab….4) baaaaabaa
• A.

1, 2 and 3

• B.

2, 3 and 4

• C.

1, 2 and 4

• D.

1, 3 and 4

• 11.
Which of the following problems are decidable?….1) Does a given program ever produce an output?….2) If L is a context-free language, then is L’ (complement of L) also context-free?….3) If L is a regular language, then is L’ also regular?….4) If L is a recursive language, then, is L’ also recursive?
• A.

1, 2, 3, 4

• B.

1, 2

• C.

2, 3, 4

• D.

3, 4

• 12.
Let P be a regular language and Q be context-free language such that Q  P. (For example, let P be the language represented by the regular expression p*q* and Q be {pnqn|n  N}). Then which of the following is ALWAYS regular?
• A.

P   Q

• B.

P – Q

• C.

* – P

• D.

* – Q

• 13.
Consider the language L1,L2,L3 as given below.L1={ | p,q  N}L2={ | p,q  N and p=q}L3={ | p,q,r  N and p=q=r}Which of the following statements is NOT TRUE?
• A.

Push Down Automata (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 machine can be used to recognize all the three languages

• 14.
S –> aSa| bSb| a| b ;The language generated by the above grammar over the alphabet {a,b} is the set of
• A.

All palindromes.

• B.

All odd length palindromes.

• C.

Strings that begin and end with the same symbol

• D.

All even length palindromes.

• 15.
Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)*?
• A.

The set of all strings containing the substring 00.

• B.

The set of all strings containing at most two 0’s.

• C.

The set of all strings containing at least two 0’s.

• D.

The set of all strings that begin and end with either 0 or 1.

• 16.
Which one of the following is FALSE?
• A.

There is unique minimal DFA for every regular language

• B.

Every NFA can be converted to an equivalent PDA.

• C.

Complement of every context-free language is recursive.

• D.

Every nondeterministic PDA can be converted to an equivalent deterministic PDA.

• 17.
Match all items in Group 1 with correct options from those given in Group 2.Group 1 Group 2 P. Regular expression 1. Syntax analysis Q. Pushdown automata 2. Code generation R. Dataflow analysis 3. Lexical analysis S. Register allocation 4. Code optimization
• A.

P-4. Q-1, R-2, S-3

• B.

P-3, Q-1, R-4, S-2

• C.

P-3, Q-4, R-1, S-2

• D.

P-2, Q-1, R-4, S-3

• 18.
How many strings of length less than 4 contains the language described by the regular expression (x+y)*y(a+ab)*?
• A.

7

• B.

10

• C.

12

• D.

11

• 19.
Which of the following is true?
• A.

(01)*0 = 0(10)*

• B.

(0+1)*0(0+1)*1(0+1) = (0+1)*01(0+1)*

• C.

(0+1)*01(0+1)*+1*0* = (0+1)*

• D.

All of the mentioned

• 20.
A language is regular if and only if
• A.

Accepted by DFA

• B.

Accepted by PDA

• C.

accepted by LBA

• D.

Accepted by Turing machine

• 21.
Let the class of language accepted by finite state machine be L1 and the class of languages represented by regular expressions be L2 then
• A.

L1

• B.

L1>=L2

• C.

L1 U L2 = .*

• D.

L1=L2

• 22.
Which of the following is not a regular expression?
• A.

[(a+b)*-(aa+bb)]*

• B.

[(0+1)-(0b+a1)*(a+b)]*

• C.

(01+11+10)*

• D.

(1+2+0)*(1+2)*

• 23.
Regular expression are
• A.

Type 0 language

• B.

Type 1 language

• C.

Type 2 language

• D.

Type 3 language

• 24.
Which of the following is true?
• A.

Every subset of a regular set is regular

• B.

Every finite subset of non-regular set is regular

• C.

The union of two non regular set is not regular

• D.

Infinite union of finite set is regular

• 25.
L and ~L are recursive enumerable then L is
• A.

Regular

• B.

Context free

• C.

Context sensitive

• D.

Recursive

Related Topics Back to top