Ask
Login
0
2.7kviews
Design a DFA that rejects any string over {1,2,3} where 2 is immediately preceded by a 1. It should accept all other strings.
written 8.0 years ago by gravatar for teamques10 teamques10 ★ 70k •   modified 3.9 years ago
automata theory
ADD COMMENT EDIT
1 Answer
0
99views
written 8.0 years ago by gravatar for teamques10 teamques10 ★ 70k

$\epsilon$-NFA for the problem is \ltcenter\gt![enter image description here][1]\lt/center\gt | S | {B,C} | {B.C} | {B.C} | |---|---------|--------|---------| | A | {B.C} | {B.C} | {B.C} | | B | {D} | $\Phi$ | $\Phi$ | | C | {D} | $\Phi$ | $\Phi$ | | D | {E,F,G} | $\Phi$ | {E,F,G} | | E | {G,H} | {G,H} | {G,H} | | F | {G,H} | {G,H} | {G,H} | | G | $\Phi$ | $\Phi$ | $\Phi$ | | H | $\Phi$ | $\Phi$ | $\Phi$ |

S:

enter image description here

A:

enter image description here

B:

enter image description here

C:

enter image description here

D:

enter image description here

E:

enter image description here

F:

enter image description here

G:

enter image description here

H:

enter image description here

NFA is given as

enter image description here

States\Inputs 1 2 3
S {B,C} {B,C} {B,C}
A {B,C} {B,C} {B,C}
B {D} {I} {I}
C {D} {I} {I}
D {E,F,G} {I} {E,F,G}
E {G,H} {G,H} {G,H}
F {G,H} {G,H} {G,H}
G {I} {I} {I}
H {I} {I} {I}
I {I} {I} {I}

Final DFA is

enter image description here
ADD COMMENT EDIT
Please log in to add an answer.