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.