Let $L \subseteq \{a,b \}^* $ be a rational language. Show that $K$ is rational.

Question

Let $L \subseteq \{a,b \}^* $ be a rational language. $K$ the subset of words in $L$ that does not have has a factor $a^2$ and $b^3$. Show that $K$ is rational.

If $A$ is a DFA that accepts L. I think we can modify it in order to get a new automaton that recognizes $K$. I just don't know how.

Answer 1

You need to check two things for a word to be in $K$: that the word is in $L$, and then that it doesn't contain $a^2$ or $b^3$. (Or you could view the second thing as two separate tasks, so there are 3 things to check).

How can you make an automata that checks all those things, and only accepts if they all hold?

(Or, as @emesupap says in a comment, you can phrase this in terms of closure properties of regular languages. But you can also just describe the DFA.)

Answer 2

Consider a DFA $A_L$ representing L. To build a DFA $A_K$ representing $K$ we transform $A_L$ as follows:

Consider a state $S$, such that there is a transition on input 'a' both to and from $S$. Now replace $S$ with a pair $S_1,S_2$ and rearrange the transitions so that.

1. $S_1$ has all the incoming transitions of $S$ except on input 'a'.
2. $S_1$ has all outgoing transitions of $S$, including on 'a'.
3. $S_2$ has all incoming transitions of $S$ on input 'a'.
4. $S_2$ has all outgoing transitions of $S$ except on 'a'.

Note: when there is an 'a'-transition from $S$ to $S$ (loop), the above scheme implies an 'a'-transition from $S_1$ to $S_2$.

The above process reduces the number states allowing $a^2$ by one. Repeating it will eliminate all such states. To prove that the this construction satisfies the problem we can show that on every step $K_i \subseteq L$, and that every string from $L$ but without $a^2$ and $b^3$ can be mapped to $K_i$ (where $K_i$ is the language correponding to the DFA constructed in the $i$-th step).

To eliminate $b^3$ we can follow a similar but more complicated approach which generally eliminates two states involved in parsing $b^3$, or one state in the case when $b^3$ can be generated by a single state with a loop on 'b'. This approach is illustrated in the attached drawing.

The above steps reduce the number of states which are used to parse $a^2$ and $b^3$, but preserve all other strings from $L$. Since the number of states is finite we can eliminate all such states, which will disallow $a^2$ and $b^3$ altogether.