0
$\begingroup$

I'm having a few problems with this proof and I'm not sure where to start.

In our class, a Deterministic Finite Automata, or DFA, is defined as a 5-tuple

$$M = (Q,\Sigma,\delta, q_0, F) $$

Where $Q$ is a set of states, $\Sigma$ is a set of symbols, $\delta$ is a transition function between states, $q_0$ is the starting state, and $F$ is a set of accepting states for the DFA.

The problem in my assignment is as follows:

A DFA is given with a transition function $\delta$ , which is a function from $$ Q * \Sigma \to Q $$ We extend the domain of the defi nition of $$ \hat\delta : Q * \sideset{}{^*}\Sigma \to Q$$ That is for every pair $<q,s>$, where $ q \in Q $ and $s$ is any string of symbols over $\Sigma$, the extended function value $$ \hat\delta (q, s) \in Q$$ is defi ned as follows: $$\hat\delta (q, \varepsilon ) = q $$ and $$ \hat\delta (q, xa) = \delta ( \hat\delta (q, x), a)$$ The de finition intends to capture the notion of a DFA starting with any state $q$, and after reading a string $s$, reaches state $\hat\delta (q, s)$

Prove by induction on the length of the string that for all $q \in Q $ and all strings $x$ and $y$,

$$\hat\delta (q, xy) = \hat\delta ( \hat\delta (q, x), y)$$ where $xy$ is the concatenation of $x$ and $y$.

My current problem is that I don't know where to start induction. It says to perform induction on the length of the string but it isn't clear to start on string $x$ or string $y$. Also, I am bad at induction.

$\endgroup$
2
$\begingroup$

Choose any string $x \in \Sigma^*$ and let $y \in \Sigma^n$ have length $n \geq 0$. We proceed by induction on $n \geq 0$.

Base Case: For $n = 0$, we have that $y = \varepsilon$. (Fill in the rest here.)

Induction Step: Assume that the claim holds for $n' = n - 1$, where $n \geq 1$. It remains to show that it holds for $n' = n$. Indeed, let $y = za$, where $z \in \Sigma^{n - 1}$ has length $n - 1$ and $a \in \Sigma$ has length $1$. Then it follows that: \begin{align*} \hat\delta(\hat\delta(q, x), y) &= \hat\delta(\hat\delta(q, x), za) \\ &= \delta(\hat\delta(\hat\delta(q, x), z), a) \\ &= \cdots \text{fill the rest in here} \cdots \\ &= \hat\delta(q, xza) \\ &= \hat\delta(q, xy) \end{align*}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.