The following DFA is a lexical analyzer which is supposed to recognize comments. The lexical analyzer will ignore the comment and goes back to the state one. I'm told that there's something wrong with it but I can't figure it out. What's the problem?

enter image description here

FWIW, those tiny signs are stars which are necessary for C-style comment: "/* comment */"
The loop in the state three is "except *"

  • There is no initial state, so there's no automaton. I suppose $1$ is the initial state.
  • From state 4 you can still read several times the symbol $*$ and accept the comment. For example, the coment /*hello*/ is being accepted, but the comment /*hello**/ is not. So you need $\delta(4,*)=4$.
  • Also, you need more transitions for the automaton to be a DFA. Remember that a DFA has a defined transition for all symbols from all states.
    • For example, you need transitions from $4$ with other symbols ($\delta(4,x)=3$ for $x\in\Sigma\smallsetminus\{*,/\}$).
    • The same goes for $1$ and $2$, but I leave that as an exercise ;-)
  • 1
    $\begingroup$ Not everybody defines DFA to be complete as doing so often unnecessarily clutters up pictures. It is obvious how to move from a non-complete DFA to a complete one (add error state and let missing edges go there). $\endgroup$ – Raphael Mar 15 '12 at 10:20
  • $\begingroup$ @Raphael doing that in this example would produce a complete DFA that does not recognize the comments as expected. For example, $\delta(4,a)=\textrm{err}$ invalidates comments like /*a*a*/. That's why completing a DFA should be done only after every transition "not defined so far" would make the DFA reject an invalid string (and never a valid one, as in this case). $\endgroup$ – Janoma Mar 15 '12 at 14:44

In state 2 there is no transition for when you encounter a character other than *. The same is true in state 4 with /.

Also it's not entirely clear what happens in state 1 if you encounter something other than /, but it looks like that's because that part's intentionally cut off.

  • $\begingroup$ It should recognize comments, so it should read * in state 2 and 4, I don't think that's the problem. Thank you for your answer anyway. $\endgroup$ – Gigili Mar 14 '12 at 23:01
  • $\begingroup$ @Gigili I kind of assumed it was meant to be part of a larger dfa that should recognize the whole language (because of the edges from state 1 that go nowhere). But either way it's still perfectly legal for a comment to contain a * that's not directly followed by a /, so state 4 should definitely be able to handle that. $\endgroup$ – sepp2k Mar 14 '12 at 23:05

First of all, $2$ should not be a final state. As it is (assuming $1$ is starting state), / is accepted.

Furthermore, you can not accept comments that contain * because after reading * you can never get back into $3$ (without reading /). Consider this automaton instead:


It is straight forward to modify it to be part of a lexer.

  • 2
    $\begingroup$ q3 shouldn't transition back to q2 if a * is read (otherwise reading **/ from q2 will transition to q3 then back to q2 and stay there). Also the way I understood the OP, the automaton can accept multiple consecutive comments (thus the loop back to the starting state in the original automaton). $\endgroup$ – sepp2k Mar 15 '12 at 11:26
  • $\begingroup$ Right; I fixed the automaton, thanks. Regarding integration into a lexer, I think it is reasonable to leave that as an exercise. Once the partial automaton is correct, there is not much left to do. $\endgroup$ – Raphael Mar 15 '12 at 11:36

Your DFA will not accept the comment /*hello*world*/ as δ(4,"w") = undefined.

Also, your accepting state looks like it's in the wrong place. Right now your DFA will only accept if the last character of the input is / (so / and /**// would be accepting but /**/ would not.

Assuming that it should accept on the completion of a comment, the correct DFA looks like this:

enter image description here

Similarly, if you want to recognize one or more comments, you would make 1 your accepting state and δ(4, /) = 1 (instead of 5)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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