1

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,

Can
  • 171
  • 1
    What are your own thoughts? – Harald Hanche-Olsen Dec 23 '13 at 22:05
  • Well I draw a NFA for that but it took me for a while and I am not sure it is correct. I think it would be nice to see solution with pumping lemma. My problem is I don't know how should I express this language for pumping lemma. Thank you. – Can Dec 23 '13 at 22:10
  • 1
    (aa)*(b|aba)(aa)* works, I think. – Snowball Dec 23 '13 at 22:13
  • Dear Snowball thanks for your answer. However, I could not get what do you mean by this expression.Could you explain it bit further please. Thanks. – Can Dec 23 '13 at 22:16
  • 1
    I thought the pumping lemma was typically used to show that a language is not regular? – Harald Hanche-Olsen Dec 23 '13 at 22:18
  • @CanEldem: That's a regular expression. Any language that can be represented by a regular expression is regular. If you look around online, you may be able to find instructions to convert a regular expression into a NFA or DFA. – Snowball Dec 23 '13 at 22:20
  • Dear Harald; You are right but I believe we can proof regularity of language with pumping lemma also. After we pump up or pump down if resulted string is still in language it means it is regular is not it ? – Can Dec 23 '13 at 22:21

3 Answers3

1

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.

Community
  • 1
J.-E. Pin
  • 40,163
0

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.

Harald Hanche-Olsen
  • 31,960
0

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.)

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

Snowball
  • 3,078
  • 18
  • 37
  • Thanks a million Snowball. I draw different NFA from this but this is working. Thanks again. – Can Dec 23 '13 at 22:46
  • The regular expression is correct, but the automaton could be much simpler! – J.-E. Pin Dec 24 '13 at 10:26
  • @J.-E.Pin: I just converted it semi-mechanically from the regular expression. In fact, it looks pretty similar to the one generated here if you put in that regex. – Snowball Dec 24 '13 at 20:58
  • @Snowball For such a small example, Brzozowski's algorithm using derivatives can be done manually and it produces directly the minimal automaton. – J.-E. Pin Dec 25 '13 at 09:49