Welcome to our community

Be a part of something great, join today!

Is the DFA of the language L correct?

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,047
Hello!!! :eek:

I have to construct the DFA of the language $L=\{w \in \{a,b\}^*: \text{ each } "a" \text{ of the word w is appeared only after and before a } "b"\}$.

I tried the following...Could you tell if it's right?
But is it deterministic? From the second state where do we go with $a$ ?
 

Attachments

Last edited:

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
Re: Is the DFA of the language $L$ correct?

I have to construct the DFA of the language $L=\{w \in \{a,b\}^*: \text{ each } "a" \text{ of the word w is appeared only after and before a } "b"\}$.
Immediately after and before a b, or can there be symbols between them?

I tried the following...Could you tell if it's right?
This automaton accepts ab where a is not preceeded by a b..

But is it deterministic? From the second state where do we go with $a$ ?
If consecutives a's are not allowed then there should an arrow to the "sink" state that is not accepting and from which there is no escape.
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,047
Re: Is the DFA of the language $L$ correct?

Immediately after and before a b, or can there be symbols between them?

This automaton accepts ab where a is not preceeded by a b..
This is the pronunciation of the exercise.
What I understand is that $aa $ is not allowed but $bb$ or $bba$ or $abbb$ or $babb$ is allowed..
Am I wrong?
 

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
Re: Is the DFA of the language $L$ correct?

This is the pronunciation of the exercise.
...
Am I wrong?
In general, we can only help with mathematical questions. I can't help clarify what a certain person meant when he/she devised a particular exercise, especially if there is a chance that there is a language barrier.

To me, the most natural way to interpret the exercise is that each a must be immediately preceded and immediately followed by a b.

What I understand is that $aa $ is not allowed but $bb$ or $bba$ or $abbb$ or $babb$ is allowed.
The strings $bba$ or $abbb$ should not be allowed because a is not surrounded by b's.
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,047
Re: Is the DFA of the language $L$ correct?

In general, we can only help with mathematical questions. I can't help clarify what a certain person meant when he/she devised a particular exercise, especially if there is a chance that there is a language barrier.

To me, the most natural way to interpret the exercise is that each a must be immediately preceded and immediately followed by a b.

The strings $bba$ or $abbb$ should not be allowed because a is not surrounded by b's.
Ok...I tried it again... Is it now correct?
 

Attachments

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
Re: Is the DFA of the language $L$ correct?

I believe that the empty word should be acceptable because every $a$ (there is none) is surrounded by $b$'s. Also, there is still no arrow to the sink state when $a$ is read in the third state. Finally, why not make $b$ go from the third state back to the second one? Why do you need another accepting state?
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,047
I believe that the empty word should be acceptable because every $a$ (there is none) is surrounded by $b$'s. Also, there is still no arrow to the sink state when $a$ is read in the third state. Finally, why not make $b$ go from the third state back to the second one? Why do you need another accepting state?
Do you mean something like that?
 

Attachments

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
Yes. And the arrows for $a$ and $b$ from the bottom state to itself.
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,047