0

I have to draw this automaton ( can be deterministic or not) where L is the language on the alphabet {a,b} and where the words that starts with an a have an even length ( ex: aabbab) and the words that starts by a b have an odd length (ex: baa).

This is what i tried, could someone tell me if i am correct. It seems ok to me. Thanks a lot.

enter image description here

codetime
  • 335
  • 2
  • 8
  • @gt6989b Thanks for reply, but it said in the question that the automaton can be non-deterministic, so this would work right ? Thanks. – codetime Sep 29 '20 at 03:16
  • yes, makes sense, sorry overlooked – gt6989b Sep 29 '20 at 03:30
  • Your machine is not correct: it accepts $aa$, and it also accepts $b$. But a different 4-state machine will work. – BrianO Sep 29 '20 at 03:35
  • @BrianO: It’s supposed to accept $aa$ and $b$. – Brian M. Scott Sep 29 '20 at 03:40
  • 5
    It works, but it’s more complicated than necessary: you can simply delete state $4$ and the transitions associated with it. – Brian M. Scott Sep 29 '20 at 03:41
  • 2
    @BrianM.Scott Oops yes I had the polarity reversed, my bad. – BrianO Sep 29 '20 at 03:43
  • @BrianO oh you're right state 4 is useless, thanks a lot :) – codetime Sep 29 '20 at 03:47
  • 1
    @codetime You mean to thank BrianM.Scott :) – BrianO Sep 29 '20 at 03:55
  • What is the status of the empty word? Should it be accepted or not? – J.-E. Pin Sep 29 '20 at 06:46
  • @J.-E.Pin that's a good question, i am a bit confused with this one since, if it's empty there's an even number of letters but it doesn't start with an a tho ? – codetime Sep 29 '20 at 13:27
  • Basically, it just means that your definition of $L$ is incomplete. You have to say whether $L$ contains the empty word or not separately. – J.-E. Pin Sep 29 '20 at 14:00
  • @J.-E.Pin That's the only info i have : words that start by a "a" have an even length of letters and words that starts by a "b" have an odd length. My opinion is that they cannot be empty because the language says the words that start by a b or a, if they are empty it doesn't start by any of those. What do you think ? Thanks. – codetime Sep 29 '20 at 15:08

0 Answers0