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.