1
$\begingroup$

Let assume that I have given DFA $D$ which recognize language $L$. Now I would like create the DFA/NFA which recognize the language $L'$. $$ L' = \{ w \in L : |w| = 2k, k \ge 0 \}$$ In words, $L'$ contains words form $L$ of even length. So I imagine NFA like:

Automaton diagram

And now, the "green" automata recognize if length of word is even. If yes it take a accepted state ( Q1). And the second condition is such that DFA $D$ recognize if the word is acceptable by $L$. If yes, the NFA take state $Q4$

And now: $e$ means a empty word.

blue arrows are connected with the acceptable state in D with my state Q4.

So my NFA recognize word iff the machine has a Q1 AND Q4 state. I don't know how to get AND relation.

$\endgroup$
1
$\begingroup$

As you observed, you get an OR relation by doing a disjoint sum, as in your diagram. To get an AND relation, you must take the product of the two automata. The product of $A$ and $B$ has states that are pairs of states, one from $A$ and one from $B$, so that it tracks the states of $A$ and $B$ together. Then it can accept if it is in a state $\langle a,b\rangle$ where $A$ would accept in state $a$ AND if $B$ would accept in state $b$.

If this isn't clear, please leave a comment.

$\endgroup$
  • 1
    $\begingroup$ I guess it was clear enough then. $\endgroup$ – MJD Mar 26 '15 at 15:02
  • $\begingroup$ Yes, it's clear. Thanks. :) Could you recommend me some tasks to use Myhill-Nerode Theorem? $\endgroup$ – user180834 Mar 26 '15 at 15:08
  • 1
    $\begingroup$ Usually you use the M-N theorem to prove that a certain language is, or is not, regular. So look in your book for exercises of the type "Show that language $L$ is regular" or "Is language $L$ regular?" and then try to apply the Myhill-Nerode theorem. $\endgroup$ – MJD Mar 26 '15 at 15:44

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.