I want to make the regular expression of this language but I can't: I tried but the regular expression didn't match some strings that it should. Is it even possible?

enter image description here

  • $\begingroup$ Every DFA/NFA can be converted to a regular expression and there are standard techniques for doing this. See the linked question. $\endgroup$ Commented Oct 31, 2018 at 9:49
  • $\begingroup$ i make a regular expression but every possible strings are not generated by them and i consult to a teacher i also could not $\endgroup$
    – user5948
    Commented Oct 31, 2018 at 9:54
  • $\begingroup$ Have you tried following (one of) the answers in the link given by @DavidRicherby? If yes, can you give a detailed account how much you have done and where you are stuck? (By the way, welcome to Computer Science!) In fact, image is not very welcomed here since it makes your question impossible to search and difficult to edit or copy. You are expected to transcribe text and mathematics (by LaTeX usually). $\endgroup$
    – John L.
    Commented Oct 31, 2018 at 13:56
  • $\begingroup$ @Apass.Jack The information in the image is inherently pictorial. I can't see any other reasonable way of presenting it. In particular, something like the transition table of the automaton would be much less intuitive and still not searchable. $\endgroup$ Commented Oct 31, 2018 at 15:29

1 Answer 1


Every DFA can be converted to a regular expression, so you must have made a mistake when you converted. The conversion is quite fiddly, so making a mistake with a nine-state automaton is easy to do, unfortunately.

It might help if you split the automaton in two: if the automaton accepts, it either reads an $a$ and then accepts using only states $2,4,6,\omega$ or it reads a $b$ and then accepts using only states $3,5,7,\omega$. So the regular expression must be something of the form $aR_{\{2,4,6,\omega\}}+bR_{\{3,5,7,\omega\}}$, where $R_S$ is the regular expression for the automaton that just has the states in $S$. Now, you just have to convert two nearly identical four-state automata, which should be easier to do correctly.

  • $\begingroup$ it seems you are accepting the existence of final and start to be granted. i am confused to see how you can make regular expression without declaring the final and start state of automata $\endgroup$
    – rballiwal
    Commented Oct 31, 2018 at 13:28
  • $\begingroup$ @rajendra I'm assuming that, in the diagram in the question, the state marked with "-" is the start state (note that it has no incoming transitions) and the states marked with "+" are accepting. I've never seen that convention before but, as you say, the question doesn't make a whole lot of sense, otherwise. $\endgroup$ Commented Oct 31, 2018 at 15:31
  • $\begingroup$ a(a+b)b((a+b)*+b(a+b)a((a+b)a)* i had make this RE but it cant generate all possible strings $\endgroup$
    – user5948
    Commented Nov 1, 2018 at 10:28
  • $\begingroup$ @Salma That's almost correct. The problem is that states 4, 5, 6 and 7 are all accepting but your RE looks like it only has 4 and 5 accepting. $\endgroup$ Commented Nov 1, 2018 at 10:35
  • $\begingroup$ how i can correct it? $\endgroup$
    – user5948
    Commented Nov 1, 2018 at 10:38

Not the answer you're looking for? Browse other questions tagged or ask your own question.