I am working on some Automata practice problems. I am working a 2 part question. Here it is:
Let $\Sigma = \{a,b\}$ be an alphabet. Let $L = \left\{w \in \Sigma^* \mid n_a(w) \le 4\right\}$
a) Create a transition graph for $L$
b) Find a regular expression for $L$
Here is my solution. I am no too sure about part b. If anyone can help me out, I'd really appreciate it. Thank you.
Your work for (a) is fine, but your regular expression is wrong: its last term matches $aaaaa$, for instance, which is not in $L$, and none of it matches $bab$, which is in $L$. It looks as if you tried to generate it from the transition graph and made quite a few mistakes; in particular, it looks as if you forgot to keep track of which states in the original DFA are acceptor states. In this case the language is simple enough that it’s probably easier just to write it down from scratch.
First, $b^*$ covers every word in $L$ that has no $a$s. The words with exactly one $a$ can have any number of $b$s before or after that $a$; they’re covered by $b^*ab^*$. The words with exactly two $a$s can have any number of $b$s before the first $a$, between the two $a$s, or after the second $a$; they’re covered by $b^*ab^*ab^*$. The cases of three and four $a$s are handled similarly, and you end up with
$$b^*+b^*ab^*+b^*ab^*ab^*+b^*ab^*ab^*ab^*+b^*ab^*ab^*ab^*ab^*\;.$$