0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Every DFA/NFA can be converted to a regular expression and there are standard techniques for doing this. See the linked question. $\endgroup$ – David Richerby Oct 31 '18 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 Oct 31 '18 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. Oct 31 '18 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$ – David Richerby Oct 31 '18 at 15:29
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\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$ – Noob Oct 31 '18 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$ – David Richerby Oct 31 '18 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 Nov 1 '18 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$ – David Richerby Nov 1 '18 at 10:35
  • $\begingroup$ how i can correct it? $\endgroup$ – user5948 Nov 1 '18 at 10:38

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