Deck 2: Formal Languages and Automata Theory: Part B

Question 1

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.

Answer 1

The set of all strings containing at least two 0's.

Question 2

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.

Answer 2

Every nondeterministic PDA can be converted to an equivalent deterministic PDA.

Question 3

Match all items in Group 1 with correct options from those given in Group 2.
List I  List II
p. Regular Expression   1. Syntax analysis
q. Push down 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

Answer 3

P-3, Q-1, R-4, S-2

Question 4

Which of the following pairs have DIFFERENT expressive power?

A)Deterministic finite automata (DFA) and Non-Deterministic finite automata(NFA)
B)Deterministic push down automata (DPDA) and Non-deterministic pushdown automata
C)Deterministic single-tape Turing machine and Non-deterministic single-tape Turing Machine
D)Single-tape Turing machine and multi-tape Turing machine

Question 5

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=Ø

Question 6

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

Question 7

Consider the following two statements:
S₁: { 0^2n |n >= l} is a regu1ar language
S₂: { 0^m 0^n 0^(m+n) l m >= 1 and n >= 2} is a regu1ar language
Which of the following statements is correct?

A)Only S₁ is correct
B)Only S₂ is correct
C)Both S₁ and S₂ are correct
D)None of S₁ and S₂ is correct

Question 8

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

Question 9

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!

Question 10

Which of the following is true for the language {a^p} p is prine ?

A)It is not accepted by a turing machine
B)It is regular but not context free
C)It is context free but not regular
D)It is neither regular nor context free but accepted by a turing machine

Question 11

Which of the following are decidable ?
1) whether the intersection of two regular language is infinite.
2) whether a give context free language is regular
3) whether two push down automata accept the same language.
4) whether a given grammar is context free

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

Question 12

If L and L' are recursively enumerable, then L is

A)regular
B)context free
C)context sensitive
D)recursive

Question 13

Consider the CFG with {S,A,B) as the non-terminal alphabet, {a,b) as the terminal alphabet, S as the start symbol and the following set of production rules
S --> aB S --> bA
B --> b A --> a
B --> bS A --> aS
B --> aBB A --> bAA
Which of the following strings is generated by the grammar?

A)aaaabb
B)aabbbb
C)aabbab
D)abbbba

Question 14

Consider the following context free languages:
L₁ = {0^i 1^j 2^k | i+j = k}
L₂ = {0^i 1^j 2^k | i = j or j = k}
L₃ = {0^i 1^j | i = 2j+1}
Which of the following option is true?

A)L₁, L₂ and L₃ can be recognized by Deterministic Push down automata
B)L₁, L₂ can be recognized by Deterministic Push down automata
C)L₁, L₃ can be recognized by Deterministic Push down automata
D)None of the above

Question 15

Which of the following are decidable?
I. Whether the intersection of two regular languages is infinite
II. Whether a given context-free language is regular
III. Whether two push-down automata accept the same language
IV. Whether a given grammar is context-free

A)I and II
B)I and IV
C)II and III
D)II and IV

Question 16

Let be the encoding of a Turing machine as a string over ?= {0, 1}. Let L = { |M is a Turing machine that accepts a string of length 2014 }. Then, L is

A)decidable and recursively enumerable
B)undecidable but recursively enumerable
C)undecidable and not recursively enumerable
D)decidable but not recursively enumerable

Question 17

Consider three decision problems P₁, P₂ and P₃. It is known that P₁ is decidable and P₂ is undecidable. Which one of the following is TRUE?

A)P3 is decidable if P₁ is reducible to P₃
B)P3 is undecidable if P₃ is reducible to P₂
C)P3 is undecidable if P₂ is reducible to P₃
D)P3 is decidable if P₃ is reducible to P₂'s complement

Question 18

Consider the following decision problems:
(P₁) Does a given finite state machine accept a given string
(P₂) Does a given context free grammar generate an infinite number of stings
Which of the following statements is true?

A)Both (P₁) and (P₂) are decidable
B)Neither (P₁) nor (P₂) are decidable
C)Only (P₁) is decidable
D)Only (P₂) is decidable

Question 19

Which of the following statements is false?

A)Every context-sensitive language is recursive.
B)The set of all languages that are not recursively enumerable is countable.
C)The family of recursively enumerable languages is closed under union.
D)The families of recursively enumerable and recursive languages are closed under reversal

Question 20

In some programming languages, an identifier is permitted to be a letter followed by any number of letters or digits. If L and D denotes the set of letters and digit respectively. Which of the following expression defines an identifier?

A)(L + D) *
B)(L.D) *
C)L(L + D) *
D)L(L.D) *

Question 21

The number of strings of length 4 that are generated by the regular expression (0+1+|2+3+)*, where | is an alternation character and {+, *} are quantification characters, is:

A)08
B)09
C)10
D)12

Question 22

The regular grammar for the language L = {anbm | n + m is even} is given by

A)S ? S₁ | S₂ S₁ ? a S₁| A₁ A₁ ? b A₁| ? S₂ ? aaS₂| A₂ A₂ ? b A₂| ?
B)S ? S₁ | S₂ S₁ ? a S₁| aA₁ S₂ ? aaS₂| A₂ A₁ ? b A₁| ? A₂ ? b A₂| ?
C)S ? S₁ | S₂ S₁ ? aaa S₁| aA₁ S₂ ? aaS₂| A₂ A₁ ? b A₁| ? A₂ ? b A₂| ?
D)S ? S₁ | S₂ S₁ ? aa S₁| A₁ S₂ ? aaS₂| A₂ A₁ ? bb A₁| ? A₂ ? bb A₂| ?

Question 23

Consider the following identities for regular expressions: (a) (r + s)* = (s + r)* (b) (r*)* = r* (c) (r* s*)* = (r + s)* Which of the above identities are true?

A)(a) and (b) only
B)(b) and (c) only
C)(c) and (a) only
D)(a), (b) and (c)

Question 24

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)mod5 = 2 and d(s)mod7 != 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 25

The number of tokens in the following C statement is (GATE 2000) printf("i = %d, &i = %x", i, &i);

A)3
B)26
C)10
D)21