Theory Of Computation And Compiler Design Set 1 MCQs

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.