MHB Is the DFA of the language L correct?

  • Thread starter Thread starter mathmari
  • Start date Start date
  • Tags Tags
    Dfa Language
AI Thread Summary
The discussion revolves around constructing a Deterministic Finite Automaton (DFA) for the language L, defined as the set of strings over the alphabet {a, b} where each "a" must be immediately preceded and followed by a "b." Participants clarify that consecutive "a"s are not allowed, while various combinations of "b"s are permissible. There is a debate about whether strings like "bba" or "abbb" should be accepted, with consensus that they should not, as they do not meet the criteria of "a" being surrounded by "b"s. The empty string is deemed acceptable since it contains no "a"s. The conversation includes technical details about state transitions and the design of the DFA, with suggestions for improving the automaton's structure, such as ensuring proper transitions to a sink state when encountering an invalid "a." Overall, the focus is on achieving a correct and deterministic representation of the specified language.
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hello! :o

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

  • bab.png
    bab.png
    2.7 KB · Views: 104
Last edited by a moderator:
Technology news on Phys.org
Re: Is the DFA of the language $L$ correct?

mathmari said:
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?

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

mathmari said:
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.
 
Re: Is the DFA of the language $L$ correct?

Evgeny.Makarov said:
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?
 
Re: Is the DFA of the language $L$ correct?

mathmari said:
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.

mathmari said:
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.
 
Re: Is the DFA of the language $L$ correct?

Evgeny.Makarov said:
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

  • bab.png
    bab.png
    3.2 KB · Views: 89
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?
 
Evgeny.Makarov said:
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

  • bab.png
    bab.png
    3.1 KB · Views: 100
Yes. And the arrows for $a$ and $b$ from the bottom state to itself.
 
Evgeny.Makarov said:
Yes. And the arrows for $a$ and $b$ from the bottom state to itself.

Nice! Thanks a lot for your help! :o
 
Back
Top