1

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.

user180834
  • 1,453

1 Answers1

1

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.

MJD
  • 65,394
  • 39
  • 298
  • 580
  • 1
    I guess it was clear enough then. – MJD Mar 26 '15 at 15:02
  • Yes, it's clear. Thanks. :) Could you recommend me some tasks to use Myhill-Nerode Theorem? – user180834 Mar 26 '15 at 15:08
  • 1
    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. – MJD Mar 26 '15 at 15:44