regular language question

Question

Good afternoon everyone;

I am stuck with a question I could not find and answer by myself I hope you can help me. My question is

The language L = {w : w {a,b}*, |w| is odd, w has exactly one b}.

Is this a regular language if yes could you draw NFA or DFA for this. If no, how can I proof this using pumping lemma or how can I use pumping lemma to prove it is regular.

Regards,

Answer 1

Hint: You might do it with five states:

1. Seen an even number of characters, no b.
2. Seen an odd number of characters, no b.
3. Seen an even number of characters, one b.
4. Seen an odd number of characters, one b.
5. Seen two or more b's.

I leave it to you to figure out the transitions, start state, and accepting state.

Answer 2

A regular language is a language that can be expressed as a regular expression. (I recommend only reading the "Formal definition" section of that page, not the rest of it.) A regular expression for that language is $(aa)^*(b|aba)(aa)^*$.

Spend some time getting a feel for regular expressions, then try to express it as a NFA on your own. If you get stuck, I've included a solution below. (Hover your mouse over it to view.)

Double circle is the start state, $\varepsilon$ denotes empty string. The state on the far right is the accepting/final state.

Answer 3

Your language is $L = (a^2)^* (a + aba)(a^2)^*$. The transitions of the minimal automaton are $$ 1 \xrightarrow{a} 2 \xrightarrow{a} 1 \xrightarrow{b} 3 \xrightarrow{a} 4 \xrightarrow{a} 3 \qquad 2 \xrightarrow{b} 4 $$ (I let you draw it). Initial state $1$, final state $3$.

The usual pumping lemma gives only a necessary condition for a language to be regular, but there are more powerful versions giving necessary and sufficient conditions, using "block pumping properties". See Regular languages and the pumping lemma for more details.