### Theory Of Computation And Compiler Design Set 1

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: GATEL1 = {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.