Models of Computation MT23, DFAs
Flashcards
Can you give the formal definition of a DFA?
A 5-tuple $(Q, \Sigma, \delta, q _ 0, F)$ where
- $Q$ is a finite set of states
- $\Sigma$ is a finite set called the “alphabet”
- $\delta : Q \times \Sigma \to Q$ is the transition function
- $q _ 0 \in Q$ is the start state
- $F \subseteq Q$ is the set of accepting states
If $w = a _ 1 a _ 2 \cdots a _ n \in \Sigma^\star$, what does it mean for $q \xrightarrow[]{w}^\star q’$?
There exist transitions
\[q \xrightarrow[]{a _ 1} q _ 1 \xrightarrow[]{a _ 2} \cdots \xrightarrow[]{a _ n} q _ n = q'\]How can you define $L(M)$, the language recognised by some DFA $M$?
The set of strings $w$ over $\Sigma$ such that $q _ 0 \xrightarrow[]{w}^\star q$ where $q$ is an accepting state.
Suppose we have $M _ 1$ and $M _ 2$ recognising $A$ and $B$ respectively where
\[\begin{aligned}
M _ 1 &= (Q _ 1, \Sigma, \delta _ 1, q _ 1, F _ 1) \\\\
M _ 2 &= (Q _ 2, \Sigma, \delta _ 2, q _ 2, F _ 2)
\end{aligned}\]
Then how can you define a DFA that recognises both languages?
Let $M = (Q, \Sigma, \delta, q _ 0, F)$ where
\[\begin{aligned} Q &= Q _ 1 \times Q _ 2 \\\\ \delta((r _ 1, r _ 2), a) &= (\delta _ 1(r _ 1, a), \delta _ 2(r _ 2, a)) \\\\ q _ 0 &= (q _ 1, q _ 2) \\\\ F &= (F _ 1 \times Q _ 2) \times (Q _ 1 \times F _ 2) \end{aligned}\]Suppose $M$ is a DFA. How can you determine whether $ \vert L(M) \vert = k$?
- See if any accepting state is contained in a directed cycle reachable from the start state. If it is, then $ \vert L(M) \vert $ is infinite, so output “no”.
- Otherwise, let $t$ be the size of the DFA. Iterate over all words of length $t$. If exactly $k$ of them accept, output “yes”. Otherwise output “no”.
(this might be exponential time in the worst case I think, so this is not an efficient algorithm)
Draw a DFA that accepts
\[L = \\{w \in \\{0, 1\\}^\star \mid \text{every odd position of }w \text{ is } 1\\}\]
Quickly prove that if $A$ and $B$ are regular languages, then $A \cup B$ is also regular.
Use the product construction. Suppose we have $M _ 1$ and $M _ 2$ recognising $A$ and $B$ respectively where
\[\begin{aligned} M _ 1 &= (Q _ 1, \Sigma, \delta _ 1, q _ 1, F _ 1) \\ M _ 2 &= (Q _ 2, \Sigma, \delta _ 2, q _ 2, F _ 2) \end{aligned}\]then let $M = (Q, \Sigma, \delta, q _ 0, F)$ where
\[\begin{aligned} Q &= Q _ 1 \times Q _ 2 \\ \delta((r _ 1, r _ 2), a) &= (\delta _ 1(r _ 1, a), \delta _ 2(r _ 2, a)) \\ q _ 0 &= (q _ 1, q _ 2) \\ F &= (F _ 1 \times Q _ 2) \cup (Q _ 1 \times F _ 2) \end{aligned}\](this is slightly informal, since you would then need to prove that $L(M) = L(M _ 1)\cup L(M _ 2)$).