Theory of computation miscellaneous Easy Questions and Answers | Page - 4

Theory of computation miscellaneous

Consider the transition diagram of a PDA given below with input alphabet ∑ = {a, b} and stack alphabet Γ = {X, Z}. Z is the initial stack symbol. Let L denote the language accepted by the PDA.

Which one of the following is TRUE?

1. L = { aⁿ bⁿ |n ≥ 0 } and is not accepted by any finite automata
1. L = { aⁿ | n ≥ 0 } ∪ { aⁿ bⁿ | n ≥ 0 } and is not accepted by any deterministic PDA
1. L is not accepted by any Turing machine that halts on every input
1. L = { aⁿ |n ≥ 0 } ∩ { aⁿ bⁿ | n ≥ 0 } and is deterministic context-free

View Hint View Answer Discuss in Forum

Initial state is also the final state. So aⁿ is also accepted.

Correct Option: D

Initial state is also the final state. So aⁿ is also accepted.

Language L₁ is defined by the grammar: S₁ → aS₁ b | ε
Language L₂ is defined by the grammar: S₂ → abS₂ | ε
Consider the following statements:
P : L₁ is regular
Q : L₂ is regular
Which one of the following is TRUE?

1. Both P and Q are true
1. P is true and Q is false
1. P is false and Q is true
1. Both P and Q are false

View Hint View Answer Discuss in Forum

L1 has the property that no. of a’s should be equal to no. of b’s in a string, and all a’s should precede all b’s. Hence extra memory will be required to check this property of a string (Finite Automata can't be built for this type of language). Hence this is not regular language. Therefore P is False. L2 has the property that no. of a’s should be equal to no. of b’s, but order of a’s and b’s is different here, it is (ab)*, which will require no extra memory to be accepted. (Finite Automata can be built for this language). Hence L2 is regular language. Therefore Q is True.

Correct Option: C

L1 has the property that no. of a’s should be equal to no. of b’s in a string, and all a’s should precede all b’s. Hence extra memory will be required to check this property of a string (Finite Automata can't be built for this type of language). Hence this is not regular language. Therefore P is False. L2 has the property that no. of a’s should be equal to no. of b’s, but order of a’s and b’s is different here, it is (ab)*, which will require no extra memory to be accepted. (Finite Automata can be built for this language). Hence L2 is regular language. Therefore Q is True.

Let N_f and N_p denote the classes of languages accepted by non-deterministic finite automata and non-deterministic pushdown automata, respectively. Let D_f and D_p denote the classes of languages accepted by deterministic finite automata and deterministic push-down automata respectively. Which one of the following is true?

1. D_f ⊂ N_f and D_p ⊂ N_p
1. D_f ⊂ N_f and D_p = N_p
1. D_f = N_f and D_p = N_p
1. D_f = N_f and D_p ⊂ N_p

View Hint View Answer Discuss in Forum

We know that, the languages accepted by non deterministic finite automata are also accepted by deterministic finite automata. This may not be in the case of context-free languages.
Therefore, D_f = N_f and D_p ⊂ N_p

Correct Option: D

We know that, the languages accepted by non deterministic finite automata are also accepted by deterministic finite automata. This may not be in the case of context-free languages.
Therefore, D_f = N_f and D_p ⊂ N_p

Consider the following grammar G :
S → bS|aA|b
A → bA |aB
B → bB|aS| a
Let N_a (W) and N_b (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

1. {W|N_a (W) > 3N_b (W)}
1. {W|N_b (W) > 3N_a (W)}
1. {W|N_a (W) = 3k, k ∈ {0, 1, 2,...}}
1. {W|N_b (W) = 3k, k ∈ {0, 1, 2,...}}

View Hint View Answer Discuss in Forum

Here, we have
S → bS
S → baA (S → aA)
S → baaB (A → aB)
S → baaa (B → a)
Therefore, | Na (w) | = 3.
Also, if we use A → bA instead of A → aB,
S → baA
S → babA
To terminate A, we would have to use A→ aB as only B terminates at a (B → a).
S → baA
S → babA
S → babaB
S → babaa
Thus, here also, | Na (w) | = 3. So, C is the correct answer.

Correct Option: C

Here, we have
S → bS
S → baA (S → aA)
S → baaB (A → aB)
S → baaa (B → a)
Therefore, | Na (w) | = 3.
Also, if we use A → bA instead of A → aB,
S → baA
S → babA
To terminate A, we would have to use A→ aB as only B terminates at a (B → a).
S → baA
S → babA
S → babaB
S → babaa
Thus, here also, | Na (w) | = 3. So, C is the correct answer.

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

1. G is not ambiguous
1. There exist X, Y ∈ L(G) such that XY ∈ L(G)
1. There is a deterministic push-down automata that accepts L(G)
1. We can find a deterministic finite state automata that accepts L(G)

View Hint View Answer Discuss in Forum

The grammar is S → aSb | SS | ∈
(a) G is not ambiguous is false, since ∈ which belongs to L(G), has infinite number of derivation trees, which makes G ambiguous. Some derivation trees are

(b) There exists x, y ∈ L(G) such that xy ∉ L(G) is false, since S → SS, can be used derive xy, whenever x ∈ L(G) and y ∈ L(G).
(c) It is true, since this language is L(G) = { W | n_a (W) = n_b (W) and n_a (v) ≥ n_b (V) where V is any prefix of W }
This language happens to be deterministic context-free language.
∴ There exists a dpda that accepts it.
(d) It is false, as the given language is not regular.
∴ number of DFA exists to accept it.

Correct Option: C

The grammar is S → aSb | SS | ∈
(a) G is not ambiguous is false, since ∈ which belongs to L(G), has infinite number of derivation trees, which makes G ambiguous. Some derivation trees are

(b) There exists x, y ∈ L(G) such that xy ∉ L(G) is false, since S → SS, can be used derive xy, whenever x ∈ L(G) and y ∈ L(G).
(c) It is true, since this language is L(G) = { W | n_a (W) = n_b (W) and n_a (v) ≥ n_b (V) where V is any prefix of W }
This language happens to be deterministic context-free language.
∴ There exists a dpda that accepts it.
(d) It is false, as the given language is not regular.
∴ number of DFA exists to accept it.