HINT: Start with a DFA $M_0=\langle Q,\Sigma,\delta_0,s,A\rangle$ that accepts $L$. Now modify $M_0$ to get a FFA $M=\langle Q,\Sigma,P,\delta,s,A\rangle$ that is essentially identical to $M_0$ in its operation. Use $\delta_0$ to define both $P$ and $\delta$.
I’ll walk you through the argument.
Suppose that $L=\{ba^nbc^n:n\ge 1\}$ is regular. Then the pumping lemma for regular languages says that it has a pumping length $p$ such that if $w$ is any word of $L$ whose length is at least $p$ (i.e., such that $|w|\ge p$), then $w$ can be decomposed as $w=xyz$ in such a way that $|xy|\le p$, $|y|\ge 1$, and $xy^kz\in L$ for every $k\ge 0$. In order to use the pumping lemma to show that $L$ is not in fact regular, we must find a word $w$ for which this yields some contradiction. Finding such a $w$ is largely a matter of practice and experience with similar problems.
Here we can take $w=ba^pbc^p$. No matter how we split this as $w=xyz$, if $|xy|\le p$, then the $xy$ part is some initial segment of the first $p$ letters of $w$, i.e., of $ba^{p-1}$. There are now two possibilities that have to be distinguished.
- If $|x|\ge 1$, then the initial $b$ of $w$ is part of $x$, and $y=a^r$ for some $r$ such that $1\le r\le p-1$.
If this is the case, then $x=ba^s$ for some $s\ge 0$ such that $r+s\le p-1$, and $z=a^{p-r-s}bc^p$; why? Then for any $k\ge 0$ we have
$$xy^kz=ba^sa^{kr}a^{p-r-s}c^p=ba^{p-r+(k-1)r}bc^p\;.$$
You can easily check that this is in $L$ if and only if $k=1$. If $k=0$, the block of $a$s is shorter than the block of $c$s, and if $k>1$, the block of $a$s is longer than the block of $c$s; in both cases the word is not in $L$.
- If $x$ is empty, then $y=ba^r$ for some $r\le p-1$.
In this case $z=a^{p-r}bc^p$, and
$$xy^2z=y^2z=ba^rba^pbc^p\;,$$
which is plainly not in $L$. This is sufficient, but we can go further and note that in fact $xy^kz\in L$ if and only if $k=1$, so that we just have the original $w$: $xy^kz$ has $k+1$ $b$s, while every member of $L$ has exactly two $b$s.
Best Answer
Let $\mathcal{A} = (Q, \Sigma, \delta, q_0, F)$ be a DFA that recognizes $L$. Define $\mathcal{A'} = (Q', \Sigma, \delta', q_0', F')$ as follows:
Let $w \in \sqrt{L}$. This means that $w^2 = ww \in L$. We want to show that $\delta'(q_0', w) \in L'$.
Define $h(q) = \delta(q, w)$. Since $w^2 \in L$, it follows that $h^2(q_0) \in F$. Hence $h \in F'$.
What's left is to show that $\delta'(q_0', w) = h$, which can be done via induction on the length of $w$.
Finally, we should show that $F'$ only accepts elements from $\sqrt{L}$ (and not more). I'll let you work this one out. It follows from the definition of $\mathcal{A'}$.