DFA, best practice

289 Views Asked by At

Consider the following language {A,B,C} and the following regex (A|B)+C. I'm a little in doubt about which of my two examples is more correct. Or are they both equally correct? e.g.,

enter image description here

Is it allowed to have multiple letters on a transition in a DFA?

Sorry for the paint quality.

1

There are 1 best solutions below

0
On

For a regular language $L$, there are an infinite number of finite automata that recognize $L$ (just take a DFA that recognizes $L$ and add another state that transitions only to itself, for instance). However, there is a unique (up to labeling) DFA with a minimum number of states, and various algorithms for state minimization. Ceteris paribus, a DFA with fewer states would be preferable, due to being easier to understand and taking less space to store.

In this case, we have the regular expression over the alphabet $\Sigma=\{a,b,c\}$ $$R=(a\mid b)^*c, $$ which recognizes the language $$L = \{w\in\Sigma: w \text{ has exactly one } c \text{ and } w \text{ ends with a } c\}. $$ A DFA with one state must either accept the empty language or the set of all strings over $\Sigma$, i.e. $\Sigma^*$, so our automaton must have at least two states. Your second idea is on the right track. Formally, we would describe this DFA as $M=(Q, \Sigma, \delta, q_0, F)$ where $Q=\{S_1, S_2\}$ is the set of states, $\Sigma=\{a,b,c\}$ is the input alphabet, $\delta:Q\times\Sigma\to Q$ is the transition function, given by $$ \delta(q, \alpha) = \begin{cases} S_1,& q=S_1, \alpha\ne c\\ S_2,& q=S_1, \alpha = c \text{ or } q=S_2,\alpha\in\Sigma, \end{cases} $$ $q_0=S_1$ is the starting state, and $F=\{S_2\}$ is the set of final (or "accepting" states). Equivalently, we may define $M$ by a transition diagram:

$\hskip2in$

(I used the jFAST software to produce the above image.)