Formal Language & Automata Theory
.
- 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? - ProProfs]( "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?")
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? - ProProfs]( "Consider the languages L1={|i != j}, L2={|i = j}, L3 = {|i = 2j+1}, L4 = {|i != 2j}. Which one of the following statements is true?")
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? - ProProfs]( "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?")
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? - ProProfs]( "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?")
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
Questions: 7 | Attempts: 9626 | Last updated: Mar 19, 2021
-
Sample QuestionEverything is made of matter. Matter is made of...?
Questions: 11 | Attempts: 3182 | Last updated: May 25, 2021
-
Sample QuestionWhat are the four areas in which Montessori educated children usually excell in?
Questions: 20 | Attempts: 2053 | Last updated: Aug 20, 2020
-
Sample QuestionLet L = {w = (0+1)* | w has even number of 1’s}, i.e. L is the set of all bit strings with even number of 1’s. Which one of the regular expression below represents L ? (ISRO-2016)
Back to top