1
$\begingroup$

few weeks ago I had an exam in automata theory course and I've been asked to write the following non-deterministic finite automata

Write a NFA which accepts the following language - the language contains all the words (above {a, b, c}) with at least 1 appearance of the letter c, or the parity of the count of the letter a is different from the parity of the letter c.

and I answered with the following state machine:

the finite state machine I answered with

which was totally incorrect, and I'm trying to understand why. I do know there's a possibility to solve that question with 2 states machine, but I'd like to stick with the current solution. I do understand that the arrow from q2 to itself should contain c also, but does it makes the machine completely inaccurate? how would you rank that kind of solution from 1 to 20?

$\endgroup$
5
  • $\begingroup$ Are you aware that this machine is non-deterministic ? $\endgroup$ Mar 12 at 20:26
  • $\begingroup$ @YvesDaoust it can be non-deterministic. I think the requirements allow string with no c (and recognizing its parity with 0 as even) $\endgroup$
    – eeee25
    Mar 12 at 20:33
  • $\begingroup$ @YvesDaoust that's why I bolded the "or". $\endgroup$
    – eeee25
    Mar 12 at 20:40
  • $\begingroup$ Ooooops, sorry, I read and. $\endgroup$ Mar 12 at 20:42
  • $\begingroup$ "I do know there's a possibility to solve that question with 2 states machine" - what makes you think so? It seems to me that at least three states must be necessary. There are partial inputs like aba where the string is not accepted but will be if another a is received; other inputs like ab where the string is accepted but will not be if another a is received, and inputs like bc where whatever comes next, the string will always be accepted. So the strings aba, ab and bc must leave the automaton in distinct states. But three states is sufficient. $\endgroup$
    – kaya3
    Mar 13 at 6:00

2 Answers 2

2
$\begingroup$

Observe that the language can alternatively defined as the set of strings where the count of $a$ is odd or there is at least one $c$. If we have any $c$ in the string, the parity of $a$ doesn't matter – hence the parity of $a$ matters only when there are no $c$ in the string so the parity of $c$ is even. You can construct a three-state automaton fairly close to your current one:

  • $q_0$ is the initial state: even number of $a$ and no $c$ has been read. Non-accepting.
  • $q_1$ is the state where an odd number of $a$ has been read, but no $c$. Accepting.
  • $q_2$ is the state where a $c$ has been read. Accepting.

Since all strings containing any $c$ must be accepted, reading $c$ from any state should result in $q_2$. We are going to accept the string anyway, so we can stop tracking the $a$ parity, and any symbol in $q_2$ loops back to $q_2$. Apart from that, tracking the parity of $a$ is done like you do it between $q_0$ and $q_1$.

I don't believe a two-state DFA or even NFA exists for this language, as it must have at least two accepting states: one that cannot be exited (for strings that contain any $c$) and one that can be exited (for strings that contain an odd number of $a$, no $c$). However, there are clearly non-accepted strings too, so a non-accepted state is also needed.

$\endgroup$
0
$\begingroup$

You can solve the second clause with two states with meanings "same parity" vs. "different parities", both $a$ and $c$ switching between both.

But I don't see how to avoid two additional states ("odd $a$, no $c$" and "even $a$, no $c$") to handle the "at least one $c$" clause.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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