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

Theory of computation miscellaneous

Which of the following pairs have different expressive power?

1. Deterministic Finite Automata (DFA) and Nondeterministic Finite Automata (NFA)
1. Deterministic Push Down Automata (DPDA) and Nondeterministic Push Down Automata (NPDA)
1. Deterministic single-tape turing machine and nondeterministic single tape turing machine
1. Single-tape turing machine and multi-tape turing machine

View Hint View Answer Discuss in Forum

DPDA and NPDA because an NPDA cannot be converted into DPDA.

Correct Option: B

DPDA and NPDA because an NPDA cannot be converted into DPDA.

Which of the following is/are undecidable?
1. G is a CFG. Is L(G) = Φ ?
2. G is a CFG. Is L(G) = ∑* ?
3. M is a Turing machine. Is L(M) regular?
4. A is a DFA and N is an NFA. Is L(A) = L(N)?

1. 3 only
1. 3 and 4 only
1. 1, 2 and 3 only
1. 2 and 3 only

View Hint View Answer Discuss in Forum

1. G is a CFG. Is L(G) = φ ?
Decidable
2. G is a CFG. Is L(G) = S * ?
Undecidable
3. M is a Turing Machine. Is L (M) regular ?
Undecidable.
4. A is a DFA and N is an NFA. Is L(A) = L(N) ?
Decidable.
Hence, the correct answer is (d) 2 and 3 only.

Correct Option: D

1. G is a CFG. Is L(G) = φ ?
Decidable
2. G is a CFG. Is L(G) = S * ?
Undecidable
3. M is a Turing Machine. Is L (M) regular ?
Undecidable.
4. A is a DFA and N is an NFA. Is L(A) = L(N) ?
Decidable.
Hence, the correct answer is (d) 2 and 3 only.

In the context of Abstract-Systax-Tree (AST) and ControlFlow-Graph (CFG), which one of the following is TRUE?

1. In both AST and CFG, let node N₂ be the successor of node N₁. In the input program, the code corresponding to N₂ is present after the code corresponding to N₁
1. For any input program, neither AST nor CFG will contain a cycle
1. The maximum number of successors of a node in an AST and a CFG depends on the input program
1. Each node in AST and CFG corresponds to at most one statement in the input program.

View Hint View Answer Discuss in Forum

Option (a) is false when CFG contains cycle Option (b) is false as CFG can contain cycle Option (d) is false as a single node can contain block of statements.

Correct Option: C

Option (a) is false when CFG contains cycle Option (b) is false as CFG can contain cycle Option (d) is false as a single node can contain block of statements.

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 the 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 automata?

1. 10110
1. 10010
1. 01010
1. 01001

View Hint View Answer Discuss in Forum

NA

Correct Option: D

NA

A student wrote two context-free grammars G1 and G2 for generating a single C-like array declaration. The dimension of the array is at least one. For example, int a [10] [3];
The grammars use D as the start symbol, and use six terminal symbols int; id []num.
Grammar G1 Grammar G2
D → int L; D → int L;
L → id [E L → id E
E → num] E → E[num]
E → num] [E E → [num]

Which of the grammars correctly generate the declaration mentioned above?

1. Both G1 and G2
1. Only G1
1. Only G2
1. Neither G1 nor G2

View Hint View Answer Discuss in Forum

Both G₁ and G₂ can correctly generate the declarations.

Correct Option: A

Both G₁ and G₂ can correctly generate the declarations.