Formal Language & Automata Theory

40 Questions | By Rabib | Last updated: Mar 25, 2015 | Total Attempts: 259

Questions

Settings

Questions and Answers

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 {pⁿqⁿ|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