Deck 1: Formal Languages and Automata Theory: Part A

Question 1

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?

A)(0*10*1)*
B)0*(10*10*)*
C)0*(10*1*)*0*
D)0*1(10*1)*10*

Answer 1

0*(10*10*)*

Question 2

Consider the languagesL₁={0^{i}1^{j}|i != j},L₂={0^{i}1^{j}|i = j},L₃ = {0^{i}1^{j}|i = 2j+1},L4 = {0^{i}1^{j}|i != 2j}.Which one of the following statements is true?

A)Only L₂ is context free
B)Only L₂ and L₃ are context free
C)Only L₁ and L₂ are context free
D)All are context free

Answer 2

All are context free

Question 3

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

Answer 3

n+1

Question 4

Let L = L₁ \cap L₂, where L₁ and L₂ are languages as defined below: L₁ = {a^{m}b^{m}ca^{n}b^{n} | m, n >= 0 } L₂ = {a^{i}b^{j}c^{k} | i, j, k >= 0 } Then L is

A)Not recursive
B)Regular
C)Context free but not regular
D)Recursively enumerable but not context free.

Question 5

Consider the language L₁,L₂,L₃ as given below.
L₁={0^{p}1^{q} | p,q \in N}
L₂={0^{p}1^{q} | p,q \in N and p=q} L₃={0^{p}1^{q}1^{r} | p,q,r \in N and p=q=r}
Which of the following statements is NOT TRUE?

A)Push Down Automata (PDA) can be used to recognize L₁ and L₂
B)L₁ is a regular language
C)All the three languages are context free
D)Turing machine can be used to recognize all the three languages

Question 6

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?

A)k+1
B)n+1
C)2^(n+1)
D)2^(k+1)

Question 7

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

Question 8

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) $\begin{array}{|c|c|c|c|c|c|}\hline & 00 & 01 & 10 & 11 & Q \\\hline 00 & 1 & 0 & & & \\\hline 01 & & & & 1 & \\\hline 10 & 0 & & & & \\\hline 11 & & & 0 & & \\\hline\end{array}$

B) $\begin{array}{|c|c|c|c|c|c|}\hline & 00 & 01 & 10 & 11 & \mathrm{Q} \\\hline 00 & & 0 & & & 1 \\\hline 01 & & 1 & & & \\\hline 10 & & & & 0 & \\\hline 11 & & 0 & & & \\\hline\end{array}$

C) $\begin{array}{|c|c|c|c|c|c|}\hline & 00 & 01 & 10 & 11 & \mathrm{Q} \\\hline 00 & & 1 & & & 0 \\\hline 01 & & 1 & & & \\\hline 10 & & & 0 & & \\\hline 11 & & 0 & & & \\\hline\end{array}$

D) $\begin{array}{|c|c|c|c|c|c|}\hline & 00 & 01 & 10 & 11 & \mathrm{Q} \\\hline 00 & & 1 & & & 0 \\\hline 01 & & & & 1 & \\\hline 10 & 0 & & & & \\\hline 11 & & & 0 & & \\\hline\end{array}$

Question 9

Consider the following Finite State Automaton The language accepted by this automaton is given by the regular expression

A)b*ab*ab*ab
B)(a+b)*
C)b*a(a+b)*
D)b*ab*ab

Question 10

The minimum state automaton equivalent to the above FSA has the following number of states

A)1
B)2
C)3
D)4

Question 11

Which of the following languages is regular?

A){WW^R | W € {0,1}+ }
B){WW^R X | X W € {0,1}+ }
C){WW^R | X W € {0,1}+ }
D){XWW^R | X W € {0,1}+ }

Question 12

The language L = { 0^i 2 1 ^i i>-0 } over the alphabet (0,1,2) is

A)not recurcise
B)is recursive and deterministic CFL
C)is a regular language
D)is not a deterministic CFL but a CFL

Question 13

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

A)15 States
B)11 states
C)10 states
D)9 states

Question 14

If s is a string over (0 + 1)* then let n0 (s) denote the number of 0's in s and n₁ (s)the number of l's in s. Which one of the following languages is not regular?

A)L = {s € (0 + 1)*n0 (s) is a 3-digit prime
B)L = {s € (0 + 1)* | for every prefix s' of s, l 0 (s') - n₁ (s') | <= 2 }
C)L={s € (0+1)* | n0(s) - n₁(s) | <= 4}
D)L = {s € (0 + 1) | n0 (s) mod 7 = n₁ (s) mod 5 = 0 }

Question 15

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?

A)L is recursively enumerable, but not recursive
B)L is recursive, but not context-free
C)L is context-free, but not regular
D)L is regular

Question 16

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?

A)Both DHAM3 and SHAM3 are NP-hard
B)SHAM3 is NP-hard, but DHAM3 is not
C)DHAM3 is NP-hard, but SHAM3 is not
D)Neither DHAM3 nor SHAM3 is NP-hard

Question 17

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?

A)1 only
B)1 and 3
C)2 and 3
D)1,2 and 3

Question 18

Let L₁ be a regular language, L₂ be a deterministic context-free language and L₃ a recursively enumerable, but not recursive, language. Which one of the following statements is false?

A)L₁ n L₂ is a deterministic CFL
B)L₃ n L₁ is recursive
C)L₁ U L₂ is context free
D)L₁ n L₂ n L₃ is recursively enumerable

Question 19

Consider the regular language L =(111+11111)*. The minimum number of states

A)3
B)5
C)8
D)9

Question 20

Consider the languages: GATE[2005]L₁ = {wwR w €{0, 1} *1L₂ ={w#ww € {O,1}*},where # is a special symbolL₃ ={www € {0,1}*}Which one of the following is TRUE?

A)L₁ is a deterministic CFL
B)L₂ is a deterministic CFL
C)L₃ is a CFL, but not a deterministic CFL
D)L₃ is a deterministic CFL

Question 21

Consider the languages: L₁ ={a^n b^n c^m | n,m >01 and L₂ ={a^n b^m c^m |n,m> o)
Which one of the following statements is FALSE?

A)L₁ n L₂ is a context-free language
B)L₁ u L₂ is a context-free language
C)L₁ and L₂ are context-free languages
D)L₁ n L₂ is a context sensitive language

Question 22

Let L₁ be a recursive language, and let L₂ be a recursively enumerable but not a recursive language. Which one of the following is TRUE?

A)L₁' is recursive and L₂' is recursively enumerable
B)L₁' is recursive and L₂' is not recursively enumerable
C)L₁' and L₂' are recursively enumerable
D)L₁' is recursively enumerable and L₂' is recursive

Question 23

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?

A)? is in P and ? is NP-complete
B)? is NP complete and ? is in P
C)Both ? and ? are NP-complete
D)Both ? and ? are in P

Question 24

Let L₁ be a recursive language. Let L₂ and L₃ be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

A)L₂ - L₁ is recursively enumerable.
B)L₁ - L₃ is recursively enumberable
C)L₂ intersection L₁ is recursively enumberable
D)L₂ union L₁ is recursively enumberable

Question 25

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.