+1-415-670-9189

info@expertsmind.com

# Construct a DFA Assignment Help

###
Finite Automata - Construct a DFA

How do we construct a DFA

- Determine what a DFA requires to memorize in order to recognize the strings in language.

- property of strings in language

- Determine that how many states are needed to memorize what we want actually.

- final state(s) memorizes property of strings in language.

- Find how
*the thing we memorize *is changed once the next input symbol is read.

- From this change, we obtain transition function.

**Constructing a DFA: Example**

- Consider
*L*= {εω{0,1}*| w represents the binary number which is divisible by 3}.

- *L *= {0, 00, 11, 000, 011, 110, 0000, 0011, 0110, 1001, 00000, ...}.

Step 1: decide what a DFA requires to memorize

- remembering that the portion of string which has been read so far is divisible by 3

- Step 2: how many states do we require?

- 2 states remembering that

- the string which has been read is divisible by 3
- the string which has been read is indivisible by 3.

- 3 states remembering that

- the string which has been read is divisible by 3
- the string which has been read - 1 is divisible by 3.
- the string which has been read - 2 is divisible by 3.

By using 2 states

- Reading a string
*w *representing the number divisible by 3.

- The upcoming symbol is 0. *w *0, which is 2**w*, is divisible by 3.

- If
*w*=9 is divisible by 3, so is 2**w*=18.

- The upcoming symbol is 1. *w *1, which is 2**w *+1, can be divisible or cannot be divisible by 3.

- If 8 is indivisible by 3, such that is 17.
- If 4 is indivisible by 3, however 9 is divisible.
- Using these 2 states is not adequate.
- Using 3 states
- Each state remembers the remainder of number which is divided by 3.
- If the portion of the string which has been read so far, say
*w*, represents the number whose remainder is 0 (or, 1, or 2),

- If the next symbol is 0, which can be the remainder for *w *0?

- If the next symbol is 1, which can be the remainder for *w *1?

Current

number

Current

remainder

Next symbol

New number

New remainder

3n

0

0

6n

0

3n

0

1

6n+1

1

3n+1

1

0

6n+2

2

3n+1

1

1

6n+3

0

3n+2

2

0

6n+4

1

3n+2

2

1

6n+5

2

**Email based Automata assignment help - homework help**

The study of **automata** is an important area of **theory of computation**. Students feel trouble in solving **automata** questions. We at www.expertsmind.com offers **Automata** assignment help - Automata homework help and online tutoring with best qualified and experienced computer science tutor's help. We cover all topics including **Construct a DFA** in assignment help - homework help service. Get solved problems in **automata** theory with step by step answers anytime from expert tutors at expertsmind.

*the thing we memorize*is changed once the next input symbol is read.**Constructing a DFA: Example**

*L*= {εω{0,1}*| w represents the binary number which is divisible by 3}.*L*= {0, 00, 11, 000, 011, 110, 0000, 0011, 0110, 1001, 00000, ...}.

*w*representing the number divisible by 3.*w*0, which is 2*

*w*, is divisible by 3.

*w*=9 is divisible by 3, so is 2**w*=18.*w*1, which is 2*

*w*+1, can be divisible or cannot be divisible by 3.

*w*, represents the number whose remainder is 0 (or, 1, or 2),*w*0?

*w*1?

Current

number

Current

remainder

Next symbol

New number

New remainder

3n

0

0

6n

0

3n

0

1

6n+1

1

3n+1

1

0

6n+2

2

3n+1

1

1

6n+3

0

3n+2

2

0

6n+4

1

3n+2

2

1

6n+5

2

**Email based Automata assignment help - homework help**

**automata**is an important area of

**theory of computation**. Students feel trouble in solving

**automata**questions. We at www.expertsmind.com offers

**Automata**assignment help - Automata homework help and online tutoring with best qualified and experienced computer science tutor's help. We cover all topics including

**Construct a DFA**in assignment help - homework help service. Get solved problems in

**automata**theory with step by step answers anytime from expert tutors at expertsmind.