# Is the DFA of the language L correct?

#### mathmari

##### Well-known member
MHB Site Helper
Hello!!! 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

• 6.8 KB Views: 14
Last edited:

#### Evgeny.Makarov

##### Well-known member
MHB Math Scholar
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
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
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
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

• 7.7 KB Views: 12

#### Evgeny.Makarov

##### Well-known member
MHB Math Scholar
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
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

• 7.2 KB Views: 11

#### Evgeny.Makarov

##### Well-known member
MHB Math Scholar
Yes. And the arrows for $a$ and $b$ from the bottom state to itself.

#### mathmari

##### Well-known member
MHB Site Helper
Yes. And the arrows for $a$ and $b$ from the bottom state to itself.
Nice!!! Thanks a lot for your help!!! 