1
$\begingroup$

I am trying to create a DFA and a regex for this kind of exercise:

$A = \{w ∈ \{0, 1\}^* |\text{length of w is a multiple of 2 or 3}\}$. I tried to do one for $2$ and one for $3$ and then combine them, but it didn't seem to work cause I miss some cases for example $6,7$ or so. Any help would be gratefully received :D

|cite|improve this question
$\endgroup$
  • 3
    $\begingroup$ How did you try that? The standard constructions should work along the route you outline. (I'm sure we have a duplicate somewhere...) $\endgroup$ – Raphael♦ Jan 13 '16 at 15:16
0
$\begingroup$

Hint:

buid the unity automata between those two, the first one accepts all the words with even length, and the second one accepts all the words above the alphabet such that $|w|\bigg|_{3}$ Automata number one Automata number two

|cite|improve this answer
$\endgroup$
0
$\begingroup$

Creating a state machine for each and combining the two is not a bad idea. To create a state machine accepting words having length N you can have each state represent the current length mod N.

After creating the two machines you can add a state having two epsilon transitions to the starting states of both machines. This gives a NFA accepting your language.

In a final stage you use the subset construction algorithm to convert the NFA you got into a DFA.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 1) The second paragraph references the standard constructions for getting an NFA for the union of two languages you already have automata for. It's part of the proof for the fact that regular expressions and finite automata are equally expressive. 2) Isn't it called powerset construction? $\endgroup$ – Raphael♦ Jan 13 '16 at 15:18
  • $\begingroup$ It's also known as subset construction (check the Wikipedia article). $\endgroup$ – saadtaame Jan 13 '16 at 16:59
  • $\begingroup$ If you have two deterministic automata the product-construction (usually used for intersection) also works directly for the union of the languages: just change the accepting states. $\endgroup$ – Hendrik Jan Jan 13 '16 at 23:04
-1
$\begingroup$

2 4 6 8 10 12 14 16 18...

.3 .6 .9 ... 12 .. 15 .18

Observe, that multiples of 2 and 3 meet after 6 numbers. So, you can think of resetting the 'counter' for every 6 symbols.

DFA

0 is the start state. For every 6 symbols, it resets to 0.

Constructing individually for 2 and 3, and then combining works well for "NFA". But, you need to convert that NFA back to DFA.

Regular Expression, in case of NFA will be (0|1+0|1)*|(0|1+0|1+0|1)*.

In case of DFA will be, ... not so early.

Constructing the regular expression from it a bit hectic. You need to follow the rules. (See here and here). The concept is called state removal method.

|cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ The image does not depict a finite automaton. $\endgroup$ – Raphael♦ Jan 13 '16 at 15:17
  • $\begingroup$ Where is it going wrong? $\endgroup$ – azam Jan 13 '16 at 15:19
  • $\begingroup$ State diagrams of NFA need to have directed, labelled edges. $\endgroup$ – Raphael♦ Jan 13 '16 at 15:19
  • $\begingroup$ Please excuse me for that, I thought the readers will assume the labels in their mind. I constructed that image using 'paint'. $\endgroup$ – azam Jan 13 '16 at 15:20
  • $\begingroup$ Why do you want an expression for the DFA? The one from the NFA works. $\endgroup$ – Hendrik Jan Jan 13 '16 at 23:07

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