Deterministic Finite State machine for a Language

Question

2. 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

Answer 1

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.$