- Suppose L is a regular language, and M = (Q, Σ, δ, q0, A) is a deterministic finite state machine such that L(M) = L. Prove that if |Q| = 2 then one of the following hold: (i) L = ∅ (ii) ε ∈ L, or (iii) ∃a ∈ Σ such that a ∈ L. (Hint: prove one of the three hold for each possible configuration of A and q0).
This info may be useful for understanding the question:
parts of a finite automaton
• states (finite number)
• alphabet of symbols (input symbols for the input word, finite size)
• transition function (where the arrows are)
• initial state (the state that the machine starts in)
• a set of final states (indicates accept, can be more than one) more formally a finite automaton is a 5-tuple: (Q, Σ, δ, q0, A)
• Q is a finite non-empty set of states
• Σ is a finite non-empty alphabet of symbols
• δ : Q × Σ → Q is transition function
• q0 ∈ Q is initial state
• A ⊆ Q is the accepting states
if δ(q, a) = p then “ if the automaton is in state q and reads input a then it goes to state p.
example machine: Suppose our machine M = (Q, Σ, δ, q0, A) is defined as follows: Q = {q0, q1}, Σ = {a, b}, A = {q1}
Any explanation of this would be appreciated
We are told there are exactly two states, say $q_0$ and $q_1$, where $q_0$ is the initial state.
Think about the possible values of $A$, the set of final states.
If $A=\emptyset$, then $L(M)=\emptyset$.
If $q_0\in A$ then $\varepsilon \in L(M)$
If $q_1\in A$ and there is any $a\in\Sigma$ such that $\delta(q_0,a)=q_1$ then $a\in L(M)$.
The only other possibility is that $q_1\in A$, $q_0\notin A$ and there is no transition from $q_0$ to $q_1$. In this case, once again we have $L(M)=\emptyset.$