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

Theory of computation miscellaneous

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.

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.

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

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.

Which one of the following is false?

1. There is unique minimal DFA for every regular language
1. Every NFA can be converted to an equivalent PDA
1. Complement of every context-free language is recursive
1. Every non-deterministic PDA can be converted to an equivalent deterministic PDA

View Hint View Answer Discuss in Forum

(a) true, since minimal DFA for every regular language is possible.
(b) true, NFA can be converted into an equivalent PDA.
(c) CG'S are not recursive but their complements are.
(d) false, since non deterministic PDA represents, non deterministic. CFG, since NDCFG and CFG are proper subsets so conversion required.

Correct Option: D

(a) true, since minimal DFA for every regular language is possible.
(b) true, NFA can be converted into an equivalent PDA.
(c) CG'S are not recursive but their complements are.
(d) false, since non deterministic PDA represents, non deterministic. CFG, since NDCFG and CFG are proper subsets so conversion required.