1
$\begingroup$

Given the alphabet $ Λ = \{a, b\}$ construct a FSA for the following language:

$$ L=\{α∈Λ^* ∧ |α|a =even ∧ |α|b =odd\}$$

where $|α|x $ is the number of occurrences of $x$ in $α$. Basically, only strings where the number of $a$'s is even and the one of $b$'s is odd.

My attempt was the following:

enter image description here

whereas that's the solution of my teacher:

enter image description here

I wonder if mine is correct, too. I tried to follow the paths and I think that mine is working.

$\endgroup$
  • $\begingroup$ Your solution doesn't accept $aba$, but does accept $aa$. I suspect you don't understand the definition of the language. $\endgroup$ – Yuval Filmus Jan 26 '17 at 19:44
1
$\begingroup$

Your FSA would not accept the string AAB or ABBBA, or any string ending with a B or starting with AB... or starting with BA... etc., all of which it should.

One of your main issue is that you don't have any B paths out of state 1, but more problematically you only have three states, when you need at least four. This is because you have 4 different possible states, so you need at least 4 states to store all of them (odd A & odd B, odd A & even B, even A & odd B, even A & even B).

Your teacher's is correct because it has essentially divided up the responsibility of checking the parity of A's and B's to different halves. That is, you're in the top half of the graph whenever the number of A's is even, and the right half of the graph whenever the number of B's is odd. This works because each additional letter added is going to either make B go from odd to even (or vice versa) or A to go from odd to even (or vice versa).

$\endgroup$
1
$\begingroup$

Any NFA for your language contains at least 4 states, as we can show using the fooling set method. Consider the follows 4 pairs of words: $$ (b,\epsilon),(\epsilon,b),(ab,a),(a,ab). $$ For each pair $(x,y)$ we have $xy \in L$, while for every two different pairs $(x,y),(x',y')$ we have $x'y \notin L$.

Fix an NFA for $L$. For a pair $(x,y)$, choose an accepting computation, and denote by $q_x$ the state after reading $x$. I claim that $q_x \neq q_{x'}$ for different pairs $(x,y),(x',y')$. Indeed, since $xy \in L$, upon reading $y$ the NFA can reach from $q_x$ to an accepting state. If $q_{x'} = q_x$ that would imply that $x'y \in L$, contrary to fact.

It follows that any NFA for $L$ contains at least 4 different states.

$\endgroup$

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.