Draw a DFA for strings that end in 101 or 110.
Here
we have to detect the string 101 or 110 and make sure that it is the end of the
string.
1)
If on the start state we get a 0, we remain at start state (q0).
2)
If we get a 1, move to state q1.
3) On
q1, if we get a 0, go to q2 (detecting sequence 101 through q2) and if we get a
1, move to q3 (detecting sequence 110 through q3)
4)
On q2, if we get a 1, move to q4 (final state) or if we get 0, go back to q0(as
the sequence 101 is broken)
5)
On q3, if we get a 0, move to q5 (final state) or if we get a 1, stay at the
same state.
6)
At q4, if we get a 0 go to q2, because we come at q4, only after getting a 1
and if we get a 0 the sequence 101 can be formed.
Or
else if we get a 1go to q3, as sequence 110 can be formed.
7)
On q5 if we get 0, go back to q0, as the sequence is broken and if we get a 1
go to q4, as sequence 101 will be formed.
Build a DFA for divisibility by 3 tester for a binary input.
11 which is 3 in binary is divisible by 3 ie,
the remainder is 0. When it is followed by another 1 ie, 111 it becomes 7 which
is not divisible by 3 and the remainder is 1. But if 11 is followed by a 0 ie,
110 it becomes 6 which is divisible by 3 and remainder is 0. Therefore we can
say that,
|
INPUT--->
|
0
|
1
|
|
Value
|
2 * (given value)
|
2*(given value)+1
|
|
Remainder
|
(2*r) *mod 3
|
(2*r+1)*mod3
|
Note that r is the value of the remainder of the state we are in currently.
In the
figure, R0,R1,R2 are the remainders. When remainder is 0 we go on R0, when
remainder is 1, we go to R1, when remainder is 2 we go to R2.
1)
When on R0, if we get a 0 we calculate the remainder value as follows
input is 0, therefore we use (2*r)*mod 3
2*0 mod 3= 0, therefore we stay at R0. Similarly if input is 1 we use ( 2*r+1) mod 3=(2*0+1)mod
3=1, therefore we go to R1.
2)
When on R1, if we get a 0, (2*1)mod 3=2 , therefore go to R2. Or if we get 1on
R1, (2*1 +1)mod 3=0, therefore we go to R0.
3)
If on R2, we get a 0 ,(2*2)mod 3= 1, therefore we go to R1. Or if we get a 1 on
R2, (2*2+1) mod 3= 2, therefore we stay at R2.
Draw a NFA to accept language of decimal numbers
1) The
user can enter any number either with a + sign, - sign or nothing. So the first
state q0 checks for these three kinds of inputs and moves to q1.
2) On state q1, the user can enter any number
from 0 to 9 any number of times. So we stay in 2 states at the same time q1 and
q2. If the user enters a decimal point after the number it goes to q3 otherwise
on a nothing it goes to the final state and the number is accepted.
3) On
q3 after the decimal, user has to enter a number between 0 and 9 and then go to
final state q4 where numbers between 0 to 9 can be entered.
Feels free to comment if you have any doubts in the above examples.
Recommended articles:
Comments
Post a Comment