Theory Of Computation And Compiler Design Set 1
On This Page
This set of Theory of Computation and Compiler Design Multiple Choice Questions & Answers (MCQs) focuses on Theory Of Computation And Compiler Design Set 1
Q1 | Let L={w \in (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?
- (0*10*1)*
- 0*(10*10*)*
- 0*(10*1*)*0*
- 0*1(10*1)*10*
Q2 | Consider the languagesL1={0^{i}1^{j}|i != j},L2={0^{i}1^{j}|i = j},L3 = {0^{i}1^{j}|i = 2j+1},L4 = {0^{i}1^{j}|i != 2j}.Which one of the following statements is true?
- Only L2 is context free
- Only L2 and L3 are context free
- Only L1 and L2 are context free
- All are context free
Q3 | 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?
- n-1
- n
- n+1
- 2n-1
Q4 | Let L = L1 \cap L2, where L1 and L2 are languages as defined below: L1 = {a^{m}b^{m}ca^{n}b^{n} | m, n >= 0 } L2 = {a^{i}b^{j}c^{k} | i, j, k >= 0 } Then L is
- Not recursive
- Regular
- Context free but not regular
- Recursively enumerable but not context free.
Q5 | Consider the language L1,L2,L3 as given below.L1={0^{p}1^{q} | p,q \in N}L2={0^{p}1^{q} | p,q \in N and p=q} L3={0^{p}1^{q}1^{r} | p,q,r \in N and p=q=r}Which of the following statements is NOT TRUE?
- Push Down Automata (PDA) can be used to recognize L1 and L2
- L1 is a regular language
- All the three languages are context free
- Turing machine can be used to recognize all the three languages
Q6 | Definition of a language L with alphabet {a} is given as following. L= { a^{nk} | k > 0, and n is a positive integer constant} What is the minimum number of states needed in a DFA to recognize L?
- k+1
- n+1
- 2^(n+1)
- 2^(k+1)
Q7 | 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?
- 1, 2, 3, 4
- 1, 2
- 2, 3, 4
- 3, 4
Q8 | Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. For examples, 001110 and 011001 are in the language, but 100010 is not. All strings of length less than 3 are also in the language. A partially completed DFA that accepts this language is shown below. The missing arcs in the DFA are
- A
- B
- C
- D
Q9 | Consider the following Finite State AutomatonThe language accepted by this automaton is given by the regular expression
- b*ab*ab*ab
- (a+b)*
- b*a(a+b)*
- b*ab*ab
Q10 | The minimum state automaton equivalent to the above FSA has the following number of states
- 1
- 2
- 3
- 4
Q11 | Which of the following languages is regular?
- {WW^R | W € {0,1}+ }
- {WW^R X | X W € {0,1}+ }
- {WW^R | X W € {0,1}+ }
- {XWW^R | X W € {0,1}+ }
Q12 | The language L = { 0^i 2 1 ^i i>-0 } over the alphabet (0,1,2) is
- not recurcise
- is recursive and deterministic CFL
- is a regular language
- is not a deterministic CFL but a CFL
Q13 | A minimum state deterministic finite automation accepting the language L = {W |W € {0,1}* , number of 0's and 1's in W are divisible by 3 and 5 respectively has
- 15 States
- 11 states
- 10 states
- 9 states
Q14 | If s is a string over (0 + 1)* then let n0 (s) denote the number of 0’s in s and n1 (s)the number of l’s in s. Which one of the following languages is not regular?
- L = {s € (0 + 1)*n0 (s) is a 3-digit prime
- L = {s € (0 + 1)* | for every prefix s’ of s, l 0 (s’) — n1 (s’) | <= 2 }
- L={s € (0+1)* | n0(s) - n1(s) | <= 4}
- L = {s € (0 + 1) | n0 (s) mod 7 = n1 (s) mod 5 = 0 }
Q15 | For S € (0+1)* let d(s)denote the decimal value of s(e.g.d(101)= 5).Let L = {s € (0 + 1) | d (s) mod 5 = 2 and d (s) mod 7 != 4)}Which one of the following statements is true?
- L is recursively enumerable, but not recursive
- L is recursive, but not context-free
- L is context-free, but not regular
- L is regular
Q16 | Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G =(V,E)with V divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?
- Both DHAM3 and SHAM3 are NP-hard
- SHAM3 is NP-hard, but DHAM3 is not
- DHAM3 is NP-hard, but SHAM3 is not
- Neither DHAM3 nor SHAM3 is NP-hard
Q17 | Consider the following statements about the context free grammarG = {S - >SS, S - >ab, S - >ba, S - ?}I. G is ambiguousII. G produces all strings with equal number of a’s and b’sIII. G can be accepted by a deterministic PDA.Which combination below expresses all the true statements about G?
- 1 only
- 1 and 3
- 2 and 3
- 1,2 and 3
Q18 | 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?
- L1 n L2 is a deterministic CFL
- L3 n L1 is recursive
- L1 U L2 is context free
- L1 n L2 n L3 is recursively enumerable
Q19 | Consider the regular language L =(111+11111)*. The minimum number of states
- 3
- 5
- 8
- 9
Q20 | Consider the languages: GATE[2005]L1 = {wwR w €{0, 1} *1L2 ={w#ww € {O,1}*},where # is a special symbolL3 ={www € {0,1}*}Which one of the following is TRUE?
- L1 is a deterministic CFL
- L2 is a deterministic CFL
- L3 is a CFL, but not a deterministic CFL
- L3 is a deterministic CFL
Q21 | Consider the languages: L1 ={a^n b^n c^m | n,m >01 and L2 ={a^n b^m c^m |n,m> o) Which one of the following statements is FALSE?
- L1 n L2 is a context-free language
- L1 u L2 is a context-free language
- L1 and L2 are context-free languages
- L1 n L2 is a context sensitive language
Q22 | Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE?
- L1' is recursive and L2' is recursively enumerable
- L1' is recursive and L2' is not recursively enumerable
- L1' and L2' are recursively enumerable
- L1' is recursively enumerable and L2' is recursive
Q23 | Consider the following two problems on undirected graphs:?: Given G(V,E), does G have an independent set of size |v|—4??: Given G(V,E), does G have an independent set of size 5?Which one of the following is TRUE?
- ? is in P and ? is NP-complete
- ? is NP complete and ? is in P
- Both ? and ? are NP-complete
- Both ? and ? are in P
Q24 | 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?
- L2 – L1 is recursively enumerable.
- L1 – L3 is recursively enumberable
- L2 intersection L1 is recursively enumberable
- L2 union L1 is recursively enumberable
Q25 | S –> aSa| bSb| a| b ;The language generated by the above grammar over the alphabet {a,b} is the set of
- All palindromes.
- All odd length palindromes.
- Strings that begin and end with the same symbol
- All even length palindromes.