TOC - part-02

  

1. Given the language L = {ab, aa, baa}, which of the following strings are in L*?

1) abaabaaabaa

2) aaaabaaaa

3) baaaaabaaaab

4) baaaaabaa 

 1, 2 and 4

2. 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

3. 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)*?

The set of all strings containing at least two 0’s

4. Which one of the following is FALSE?

Every nondeterministic PDA can be converted to an equivalent deterministic PDA

5. Which of the following statements is false?

Every subset of a recursively enumerable set is recursive

6. Which of the following is TRUE?

Every finite subset of a non-regular set is regular

7. A minimum state deterministic finite automaton accepting the language L={w | w ε {0,1} *, number of 0s and 1s in w are divisible by 3 and 5, respectively} has

15 states

8. Let L1 = {w ∈ {0,1}∗ | w has at least as many occurrences

of (110)’s as (011)’s}. 

Let L2 = { ∈ {0,1}∗ | w has at least as many occurrences

of (000)’s as (111)’s}. 

Which one of the following is TRUE?

L1 is regular but not L2

9. The length of the shortest string NOT in the language (over Σ = {a, b}) of the following regular expression is ______________.

a*b*(ba)*a*

3

10. Consider the regular language L = (111 + 11111)*. The minimum number of states in any DFA accepting this languages is:

9

11. Let Nf and Np denote the classes of languages accepted by non-deterministic finite automata and non-deterministic push-down automata, respectively. Let Df and Dp denote the classes of languages accepted by deterministic finite automata and deterministic push-down automata, respectively. Which one of the following is TRUE?

Df = Nf and Dp ⊂ Np

12. The regular expression 0*(10*)* denotes the same set as

none of these

13. The smallest finite automation which accepts the language {x | length of x is divisible by 3} has :

3 state

14. Given an arbitary non-deterministic finite automaton (NFA) with N states, the maximum number of states in an equivalent minimized DFA is at least

2^N

15. Consider a DFA over ∑ = {a, b} accepting all strings which have number of a’s divisible by 6 and number of b’s divisible by 8. What is the minimum number of states that the DFA will have?

48

16. 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?

S = T

17. Let L denotes the language generated by the grammar S -> 0S0/00. Which of the following is true?

L is regular but not 0+

18. What can be said about a regular language L over {a} whose minimal finite state automaton has two states?

Either L must be {a^n | n is odd}, or L must be {a^n | n is even}

19. How many minimum states are required in a DFA to find whether a given binary string has odd number of 0's or not, there can be any number of 1's.

2

20. Consider alphabet ∑ = {0, 1}, the null/empty string λ and the sets of strings X0, X1 and X2 generated by the corresponding non-terminals of a regular grammar. X0, X1 and X2 are related as follows:

X0 = 1 X1

X1 = 0 X1 + 1 X2

X2 = 0 X1 + {λ} 

Which one of the following choices precisely represents the strings in X0?

1(0* + 10)*1

21. The number of states in the minimal deterministic finite automaton corresponding to the regular expression (0 + 1)*(10) is ____________

3

22. Let T be the language represented by the regular expression Σ∗0011Σ∗ where Σ = {0, 1}. What is the minimum number of states in a DFA that recognizes L' (complement of L)?

5

23. Which one of the following regular expressions is NOT equivalent to the regular expression (a + b + c) *?

((ab)* + c*)*

24. Let L be a regular language and M be a context-free language, both over the alphabet Σ. Let Lc and Mc denote the complements of L and M respectively. Which of the following statements about the language Lc∪ Mc is TRUE?

None of the above

25. Which of the following statements is TRUE about the regular expression 01*0?

It represents an infinite set of finite strings

26. The language {0^n 1^n 2^n | 1 ≤ n ≤ 10^6} is

Regular

27. A language L satisfies the Pumping Lemma for regular languages, and also the Pumping Lemma for context-free languages. Which of the following statements about L is TRUE?

None of the above

28. Consider the context-free grammar E → E + E E → (E * E) E → id

where E is the starting symbol, the set of terminals is {id, (,+,),*}, and the set of nonterminals is {E}.

Which of the following terminal strings has more than one parse tree when parsed according to the above grammar?

id + id + id + id

29. Consider the context-free grammar E → E + E E → (E * E) E → id

where E is the starting symbol, the set of terminals is {id, (,+,),*}, and the set of non-terminals is {E}.

For the terminal string id + id + id + id, how many parse trees are possible?

5

30. The number of states in the minimum sized DFA that accepts the language defined by the regular expression (0+1)*(0+1)(0+1)* is __________________ .

2

31. Consider the following two statements:

I. If all states of an NFA are accepting 

states then the language accepted by 

the NFA is Σ∗ .

II. There exists a regular language A such 

that for all languages B, A ∩ B is regular. 

Which one of the following is CORRECT?

Only II is true

32. In the context-free grammar below, S is the start symbol, a and b are terminals, and ϵ denotes the empty string S → aSa | bSb | a | b | ϵ Which of the following strings is NOT generated by the grammar?

Baba

33. Consider an ambiguous grammar G and its disambiguated version D. Let the language recognized by the two grammars be denoted by L(G) and L(D) respectively. Which one of the following is true ?

L (D) = L (G)

34. Which of the following regular expressions describes the language over {0, 1} consisting of strings that contain exactly two 1's?

0 * 10 * 10 *

35. Let N be an NFA with n states and let M be the minimized DFA with m states recognizing the same language. Which of the following in NECESSARILY true?

m ≤ 2^n

36. Consider the following languages. 

L1 = {a^i b^j c^k | i = j, k ≥ 1} 

L1 = {a^i b^j | j = 2i, i ≥ 0} 

Which of the following is true?

L1 ∩ L2 = ∅ and L1 is non-regular

37. Which of the following languages is (are) non-regular?

L1 = {0^m1^n | 0 ≤ m ≤ n ≤ 10000} 

L2 = {w | w reads the same forward and backward} 

L3 = {w ∊ {0, 1} * | w contains an even number of 0's and an even number of 1's}

L2 only

38. Which of the following intuitive definition is true about LR(1) Grammar.

For a grammar to be LR(1) it is sufficient that a left-to-right shift reduce parser be able to recognize handles of right-sentential form when they appear on the stack

39. Consider the Following regular expressions

r1 = 1(0 + 1)*

r2 = 1(1 + 0)+

r3 = 11*0

What is the relation between the languages generated by the regular expressions above ?

L (r1) ⊇ L (r2) and L(r2) ⊇ L(r3)

40. Consider regular expression r, where r = (11 + 111)* over Ʃ = {0, 1}. Number of states in minimal NFA and DFA respectively are:

NFA – 3, DFA – 4

41. Consider the grammar G.

E -> TE’

E’ -> +TE’ | ԑ

T’ -> FT’

T’ -> *FT’ | ԑ

F -> (E) | id

If LL(1) parsing table is constructed using the grammar G, then how many entries are present in the row that represents E’ nonterminal ? (consider the entries which are not error/not blank entries

3

42. Let, init (L) = {set of all prefixes of L}, 

Let L = {w | w has equal number of 0’s and 1’s} 

init (L) will contain:

all binary strings with ԑ-string

43. Suppose M1 and M2 are two TM’s such that L(M1) = L(M2). Then

On every i/p which M1 accepts, M2 halts

44. Consider the following decision problems:

(P1) Does a given finite state machine accept a given string

(P2) Does a given context free grammar generate an infinite 

number of stings

Which of the following statements is true?

Both (P1) and (P2) are decidable

45. Consider the following two statements:

Only S1 is correct

46. Which of the following statements is true ?

The union of two context free languages is context free

 

47. Consider the following languages. Which of the languages are regular?

 

Only L3

 

48. Consider the following problem X.

Given a Turing machine M over the input alphabet Σ, any

state q of M And a word w∈Σ*, does the computation of M

on w visit the state q? 

Which of the following statements about X is correct?

 

X is undecidable but partially decidable

 

49. The language accepted by a Pushdown Automation in which the stack is limited to 10 items is best described as

Regular

50. The Finite state machine described by the following state diagram with A as starting state, where an arc label is x / y and x stands for 1-bit input and y stands for 2- bit output

 

Outputs the sum of the present and the previous bits of the input.

 

51. Which of the following is true?

 

The complement of a recursive language is recursive.

 

52. The C language is:

 

A context free language

 

53. Ram and Shyam have been asked to show that a certain problem Π is NP-complete. Ram shows a polynomial time reduction from the 3-SAT problem to Π, and Shyam shows a polynomial time reduction from Π to 3-SAT. Which of the following can be inferred from these reductions ?

 

Π is NP-complete

 

54. Nobody knows yet if P = NP. Consider the language L defined as follows. Which of the following statements is true ?

 

L is recursive

 

55. If the strings of a language L can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following statements is true ?

 

L is recursive but not necessarily context free

 

56. Consider the following deterministic finite state automaton M. Let S denote the set of seven bit binary strings in which the first, the fourth, and the last bits are 1. The number of strings in S that are accepted by M is

 

7

 

57. Let G = ({S}, {a, b} R, S) be a context free grammar where the rule set R is S → a S b | SS | ε . Which of the following statements is true?

 

There is a deterministic pushdown automaton that accepts L(G)

 

58. Define languages L0 and L1 as follows :

L0 = {< M, w, 0 > | M halts on w}

L1 = {< M, w, 1 > | M does not halts on w} 

Here < M, w, i > is a triplet, whose first component. M is an encoding of a Turing Machine, second component, w, is a string, and third component, i, is a bit. Let L = L0 ∪ L1. Which of the following is true ?

 

L is recursively enumerable, but L' is not

 

59. Consider the NFA M shown below. Let the language accepted by M be L. Let L1 be the language accepted by the NFA M1, obtained by changing the accepting state of M to a non-accepting state and by changing the non-accepting state of M to accepting states. Which of the following statements is true ?

 

L1 = {0, 1}*

 

60. The following finite state machine accepts all those binary strings in which the number of 1's and 0's are respectively. 

 

divisible by 3 and 2

 

61. The language {a^m b^n C^(m+n) | m, n ≥ 1} is

 

context-free but not regular

 

62. Consider the following grammar G:

S → bS | aA | b

A → bA | aB

B → bB | aS | a 

Let Na(w) and Nb(w) denote the number of a's and b's in a string w respectively. The language L(G) ⊆ {a, b}+ generated by G is

 

{ w | Na(w) = 3k, k ∈ {0, 1, 2, ...}}

 

63. L1 is a recursively enumerable language over Σ. An algorithm A effectively enumerates its words as w1, w2, w3, ... Define another language L2 over Σ Union {#} as {wi # wj : wi, wj ∈ L1, i < j}. Here # is a new symbol. Consider the following assertions.

S1 : L1 is recursive implies L2 is recursive

S2 : L2 is recursive implies L1 is recursive 

Which of the following statements is true ?

 

Both S1 and S2 are true

 

64. Consider the languages L1 = and L2 = {a}. Which one of the following represents L1 L2* U L1*

 

A

 

65. Consider the DFA given. Which of the following are FALSE?

1. Complement of L(A) is context-free.

2. L(A) = L((11*0+0)(0 + 1)*0*1*)

3. For the language accepted by A, A is the minimal DFA.

4. A accepts all strings over {0, 1} of length at least 2. 

 

 

3 and 4 only

 

66. What is the complement of the language accepted by the NFA shown below?

 

 

B

 

67. Consider the set of strings on {0,1} in which, every substring of 3 symbols has at most two zeros. For example, 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.

Missing arcs in the DFA are

 

 

D

 

68. A deterministic finite automation (DFA)D with alphabet {a,b} is given below. Which of the following finite state machines is a valid minimal DFA which accepts the same language as D?

 

A

 

69. Given the following state table of an FSM with two states A and B, one input and one output.

If the initial state is A=0, B=0, what is the minimum length of an input string which will take the machine to the state A=0, B=1 with Output = 1?

 

3

 

70. Given below are two finite state automata (→ indicates the start state and F indicates a final state)Which of the following represents the product automaton Z×Y?

 

 

A

 

71. Match the following NFAs with the regular expressions they correspond to

1. ϵ + 0(01*1 + 00) * 01*

2. ϵ + 0(10 *1 + 00) * 0

3. ϵ + 0(10 *1 + 10) *1

4. ϵ + 0(10 *1 + 10) *10 *

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

 

72. Which of the following are regular sets?

 

I and IV only

 

73. Which of the following languages is regular?

C

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

C

 

75. Which one of the following is TRUE?

C

 

76. Consider the following statement:

 

{q0, q1, q2}

 

77. Which of the regular expressions given below represent the following DFA? 

I) 0*1(1+00*1)*

II) 0*1*1+11*0*1

III) (0+1)*1

I and III only

 

78. Which one of the following is CORRECT?

 

Only (I)

 

79. 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 1’s in s. Which one of the following languages is not regular?

 

D

 

80. consider the machine M given below. The language recognized by M is :

{w ∈ {a, b}* every a in w is followed by at least two b’}

 

81. The following diagram represents a finite state machine which takes as input a binary number from the least significant bit. Which one of the following is TRUE?

 

It computes 2's complement of the input number

 

82. The following finite state machine accepts all those binary strings in which the number of 1's and 0's are respectively

 

divisible by 3 and 2

 

83. Consider the following Deterministic Finite Automata. Which of the following is true?

 

It only accepts strings with substring as "aababb"

 

84. Consider the DFAs M and N given below. The number of states in a minimal DFA that accepts the language L(M) ∩ L(N) is __________.

 

1

 

85. If the final states and non-final states in the DFA below are interchanged, then which of the following languages over the alphabet {a,b} will be accepted by the new DFA? 

 

Set of all strings that do not end with ab

 

86. Consider the following two finite automata. M1 accepts L1 and M2 accepts L2. Which one of the following is TRUE?

 

 

L1 = L2

 

87. Consider the following languages. Which one of the following statements is FALSE?

 

Complement of L1 is context-free but not regular

 

88. Consider the below problem:

 

C

 

89. Consider the following question

 

 

All the three languages are context free

 

90. Consider the languages L1 = {0^i1^j | i != j}. L2 = {0^i1^j | i = j}. L3 = {0^i1^j | i = 2j+1}. L4 = {0^i1^j | i != 2j}.

 

All are context free

 

91. S -> aSa|bSb|a|b; The language generated by the above grammar over the alphabet {a,b} is the set of

 

All odd length palindromes

 

92. Consider the below question:

 

Context free but not regular

 

93. The language L= {0^i21^i | i≥0 } over the alphabet {0,1, 2} is:

 

is recursive and is a deterministic CFL

 

94. 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?

 

Aabbab

 

95. Consider the below statement:

 

L2 and L3

 

96. Consider the following statements about the context free grammar

G = {S → SS, S → ab, S → ba, S → Ε}

I. G is ambiguous

II. G produces all strings with equal number of a’s and b’s

III. G can be accepted by a deterministic PDA.

Which combination below expresses all the true statements about G?

 

I and III only

 

97. Which one of the following grammars generates the language L = {a^ib^j | i ≠ j}

 

D

 

98. Consider the languages:

L1 = {a^nb^nc^m | n, m > 0} 

L2 = {a^nb^mc^m | n, m > 0} 

Which one of the following statements is FALSE?

 

L1 ∩ L2 is a context-free language

 

99. Consider the languages:

L1 = {ww^R |w ∈ {0, 1}*}

L2 = {w#w^R | w ∈ {0, 1}*}, where # is a special symbol

L3 = {ww | w ∈ (0, 1}*)

Which one of the following is TRUE?

 

L2 is a deterministic CFL

 

100. Consider the NPDA 〈Q = {q0, q1, q2}, Σ = {0, 1}, Γ = {0, 1, ⊥}, δ, q0, ⊥, F = {q2}〉, where (as per usual convention) Q is the set of states, Σ is the input alphabet, Γ is stack alphabet, δ is the state transition function, q0 is the initial state, ⊥ is the initial stack symbol, and F is the set of accepting states, The state transition is as follows: Which one of the following sequences must follow the string 101100 so that the overall string is accepted by the automaton?

 

10010

 

101. Which of the following languages are context-free?

L1 = {a^m b^n a^n b^m ⎪ m, n ≥ 1}

L2 = {a^m b^n a^m b^n ⎪ m, n ≥ 1}

L3 = {a^m b^n ⎪ m = 2n + 1}

 

L1 and L3 only

 

102. Which one of the following statements is FALSE ?

 

Both deterministic and non-deterministic pushdown automata always accept the same set of languages

 

103. If we use internal data forwarding to speed up the performance of a CPU (R1, R2 and R3 are registers and M[100] is a memory reference), then the sequence of operations.

D

 

104. Consider the following context-free grammars. Which one of the following pairs of languages is generated by G1 and G2, respectively.

D

 

105. Consider the pushdown automaton (PDA) below which runs over the input alphabet (a, b, c). It has the stack alphabet {Z0, X} where Z0 is the bottom-of-stack marker. The set of states of the PDA is (s, t, u, f} where s is the start state and f is the final state. The PDA accepts by final state. The transitions of the PDA given below are depicted in a standard manner. For example, the transition (s, b, X) → (t, XZ0) means that if the PDA is in state s and the symbol on the top of the stack is X, then it can read b from the input and move to state t after popping the top of stack and pushing the symbols Z0 and X (in that order) on the stack.

(s, a, Z0) → (s, XXZ0)

(s, ϵ, Z0) → (f, ϵ)

(s, a, X) → (s, XXX)

(s, b, X) → (t, ϵ)

(t, b, X) → (t,.ϵ)

(t, c, X) → (u, ϵ)

(u, c, X) → (u, ϵ)

(u, ϵ, Z0) → (f, ϵ)

The language accepted by the PDA is

 

{a^lb^mc^n | 2l = m+n}

 

106. A CFG G is given with the following productions where S is the start symbol, A is a non-terminal and a and b are terminals.

S→aS∣A

A→aAb∣bAa∣ϵ

Which of the following strings is generated by the grammar above?

 

Aabbaab

 

107. Consider 2 scenarios:

C1: For DFA (ϕ, Ʃ, δ, qo, F),

if F = ϕ, then L = Ʃ*

C2: For NFA (ϕ, Ʃ, δ, qo, F),

if F = ϕ, then L = Ʃ*

Where F = Final states set

ϕ = Total states set

Choose the correct option ?

 

C1 is true, C2 is false

 

108. Let G be the CFG, l be the number of left most derivations, r be the number of right most derivations and P be the number of parse trees. Assume l , r and P are computed for a particular string. For a given CFG ‘G’ and given string ‘w’, what is the relation between l , P , r ?

 

l = P = r

 

109. Which of the following statements is/are FALSE?

1. For every non-deterministic Turing machine, 

there exists an equivalent deterministic Turing machine.

2. Turing recognizable languages are closed under union 

and complementation.

3. Turing decidable languages are closed under intersection 

and complementation.

4. Turing recognizable languages are closed under union 

and intersection.

 

2 only

 

110. 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?

(A) L2 – L1 is recursively enumerable. 

(B) L1 – L3 is recursively enumerable 

(C) L2 ∩ L1 is recursively enumerable 

(D) L2 ∪ L1 is recursively enumerable.

 

B

 

111. Which of the following is true for the language given below:

 

It is neither regular nor context-free, but accepted by a Turing machine

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

Recursive

113. Let L be a language and L' be its complement. Which one of the following is NOT a viable possibility?

Both L and L' are r.e. but not recursive

114. Let A ≤m B denotes that language A is mapping reducible (also known as many-to-one reducible) to language B. Which one of the following is FALSE?

If A ≤m B and B is not recursively enumerable then A is not recursively enumerable

115. 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?

L is regular

116. 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' --> Complement of L1

L2' --> Complement of L2

L1' is recursive and L2' is not recursively enumerable

117. A single tape Turing Machine M has two states q0 and q1, of which q0 is the starting state. The tape alphabet of M is {0, 1, B} and its input alphabet is {0, 1}. The symbol B is the blank symbol used to indicate end of an input string. The transition function of M is described in the following table

 0 1 B

 q0  q1, 1, R q1, 1, R  Halt

 q1  q1, 1, R   q0, 1, L   q0, B, L   

The table is interpreted as illustrated below. The entry (q1, 1, R) in row q0 and column 1 signifies that if M is in state q0 and reads 1 on the current tape square, then it writes 1 on the same tape square, moves its tape head one position to the right and transitions to state q1. Which of the following statements is true about M ?

M does not halt on any string in (0 + 1)+

118. For any two languages L1 and L2 such that L1 is context free and L2 is recursively enumerable but not recursive, which of the following is/are necessarily true?

1. L1' (complement of L1) is recursive 

2. L2' (complement of L2) is recursive

3. L1' is context-free 

4. L1' ∪ L2 is recursively enumerable

1 and 4 only

119. Let X be a recursive language and Y be a recursively enumerable but not recursive language. Let W and Z be two languages such that Y' reduces to W, and Z reduces to X' (reduction means the standard many-one reduction). 

Which one of the following statements is TRUE ?

W is not recursively enumerable and Z is recursive

120. Consider the following types of languages:

L1 Regular,

L2: Context-free,

L3: Recursive,

L4: Recursively enumerable. 

Which of the following is/are TRUE?

I. L3' U L4 is recursively enumerable

II. L2 U L3 is recursive

III. L1* U L2 is context-free

IV. L1 U L2' is context-free

I, II and III only

121. Which of the following problems are decidable?

3, 4

122. 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

I and IV

123. Which of the following problems is undecidable?

Ambiguity problem for CFGs

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

undecidable but recursively enumerable

125. Which of the following problems is undecidable?

Deciding if a given context-free grammar is ambiguous

126. Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. 

Which one of the following is TRUE?

P3 is undecidable if P2 is reducible to P3

127. Consider the following statements:

1. The complement of every Turning decidable 

language is Turning decidable

2. There exists some language which is in NP 

but is not Turing decidable

3. If L is a language in NP, L is Turing decidable

Which of the above statements is/are True?

Only 1 and 3

128. Which of the following decision problems are undecidable ?

 

III and IV only

129. Let L={w ∈ (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*10*)*

130. Let P be a regular language and Q be context-free language such that Q ⊆ P. 

(For example, let P be the language represented by the regular expression p*q* and Q be {p^nq^n|n ∈ N}).

 Then which of the following is ALWAYS regular?

∑* – P

131. Consider the language L1,L2,L3 as given below.

L1={0^p1^q | p,q ∈ N}

L2={0^p1^q| p,q ∈ N and p=q}

L3={0^p1^q0^r | p,q,r ∈N and p=q=r}

Which of the following statements is NOT TRUE?

All the three languages are context free

132. 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?

n+1

133. Which of the following pairs have DIFFERENT expressive power?

Deterministic push down automata (DPDA) and Non-deterministic pushdown automata

134. 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?

3, 4

135. 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?

S=T

136. Let L denotes the language generated by the grammar S – OSO/00. Which of the following is true ?

L is regular but not O

137. Consider the following two statements:

S1: { 0^2n |n >= l} is a regular language

S2: { 0^m 0^n 0^(m+n) l m >= 1 and n >= 2} is a regular language

Which of the following statements is correct?

Both S1 and S2 are correct

138. Given an arbitrary non-deterministic finite automaton (NFA) with N states, the maximum number of states

 in an equivalent minimized DFA is at least

2^N