Consider a finite automaton F1 with three states C (start), S and E (final), in which there are transitions in both directions between every pair of states (C ⇄ S, S ⇄ E, C ⇄ E). Let F2 be the finite automaton obtained by reversal of F1. Which of the following is correct?
Pick an option to check yourself, or open the answer below.
Show answer & explanation
Correct answer: B. L(F1) = L(F2)
Explanation
Every transition of F1 has a matching transition in the opposite direction, so reversing all edges reproduces the same transition structure. The keyed answer is that the reversed automaton accepts the same language: L(F1) = L(F2).More Theory of Computation and Compilers questions
- The maximum yield length of the following CNF CFG is S → AB A → CD B → e C → a D → b
- Consider the language L = {w ∈ {a, b, c}* : nₐ(w) + n_b(w) = n_c(w)}. L is
- Consider the following statements: A. A context-free language is generated by an LR(0) grammar if and only if it is accepted by a determini…
- Which phase of the compiler checks the grammar of the program?
- Consider the following statements: A. The set of Turing machine codes for TMs that accept all inputs that are palindromes (possibly along w…
- Which of the following parsers is the most powerful?