Info-Grade: DS Notes

Finite State Automation (DFA) Contains With |Examples|

1. Construct finite state automata (DFA) that contains with abb

Solution :
Σ: inputs = {a, b}
q₀ = initial state
q₁ = string with a
q₂ = string with ab
q₃ = string with abb

Q: set of all states (q_0,q_1,q_2,q₃)
F: Final State

Transition Matrix

		f
		a	b
ε	q₀	q₁	q₀
a	q₁	q₁	q₂
ab	q₂	q₁	q₃
abb	q₃	q₃	q₃

Transition Graph

2. Construct finite state automata (DFA) that contains with aab

Solution :
Σ: inputs = {a, b}
q₀ = initial state
q₁ = string with a
q₂ = string with aa
q₃ = string with aab

Q: set of all states (q_0,q_1,q_2,q₃)
F: Final State

Transition Matrix

		f
		a	b
ε	q₀	q₁	q₀
a	q₁	q₂	q₀
ab	q₂	q₂	q₃
abb	q₃	q₃	q₃

Transition Graph

3. Construct finite state automata (DFA) that contains with aba

Solution :
Σ: inputs = {a, b}
q₀ = initial state
q₁ = string with a
q₂ = string with ab
q₃ = string with aba

Q: set of all states (q_0,q_1,q_2,q₃)
F: Final State

Transition Matrix

		f
		a	b
ε	q₀	q₁	q₀
a	q₁	q₁	q₂
ab	q₂	q₃	q₀
abb	q₃	q₃	q₃

Transition Graph

4. Construct finite state automata (DFA) that contains with aabb

Solution :
Σ: inputs = {a, b}
q₀ = initial state
q₁ = string with a
q₂ = string with aa
q₃ = string with aabb

Q: set of all states (q_0,q_1,q_2,q₃)
F: Final State

Transition Matrix

		f
		a	b
ε	q₀	q₁	q₀
a	q₁	q₂	q₀
aa	q₂	q₂	q₃
aab	q₃	q₁	q₄
aabb	q₄	q₄	q₄

Transition Graph

Finite State Automation (DFA) Ends With |Examples|

1. Construct finite state automata (DFA) that ends with abb

Solution :
Σ: inputs = {a, b}
q₀ = initial state
q₁ = string ends with a
q₂ = string ends with ab
q₃ = string ends with abb

Q: set of all states (q_0,q_1,q_2,q₃)
F: Final State

Transition Matrix

		f
		a	b
ε	q₀	q₁	q₀
a	q₁	q₁	q₂
ab	q₂	q₁	q₃
abb	q₃	q₁	q₀

Transition Graph

2. Construct finite state automata (DFA) that ends with aab

Solution :
Σ: inputs = {a, b}
q₀ = initial state
q₁ = string ends with a
q₂ = string ends with aa
q₃ = string ends with aab

Q: set of all states (q_0,q_1,q_2,q₃)
F: Final State
Transition Matrix

		f
		a	b
ε	q₀	q₁	q₀
a	q₁	q₂	q₀
aa	q₂	q₂	q₃
aab	q₃	q₁	q₀

Transition Graph

3. Construct finite state automata (DFA) that ends with aba

		f
		a	b
ε	q₀	q₁	q₀
a	q₁	q₁	q₂
ab	q₂	q₃	q₀
aba	q₃	q₁	q₂

Transition Graph

4. Construct finite state automata (DFA) that ends with aabb

Solution :
Σ: inputs = {a, b}
q₀ = initial state
q₁ = string ends with a
q₂ = string ends with aa
q₃ = string ends with aab

q₄= string ends with aabb

Q: set of all states (q_0,q_1,q_2,q_3,q4)

F: Final State

Transition Matrix

		f
		a	b
ε	q₀	q₁	q₀
a	q₁	q₂	q₀
aa	q₂	q₂	q₃
aab	q₃	q₁	q₄
aabb	q₄	q₁	q₀

Transition Graph

Finite State Automation (DFA) Starts With |Examples|

1. Construct finite state automation (DFA) that starts with 'abb'.

Solution :
Σ: inputs = {a, b}
q₀ = initial state
q₁ = string starts with a
q₂ = string starts with ab
q₃ = string starts with abb

Q: set of all states (q_0,q_1,q_2,q_3,qФ)
F: Final State

Transition Matrix

		f
		a	b
ε	p₀	p₁	qФ
a	p₁	qФ	p₂
ab	p₂	qФ	p₃
abb	p₃	p₃	p₃
	p₄	qФ	qФ

Transition Graph

2. Construct finite state automation (DFA) that starts with 'aab'.

Solution :
Σ: inputs = {a, b}
q₀ = initial state
q₁ = string starts with a
q₂ = string starts with aa
q₃ = string starts with aab

Q: set of all states (q_0,q_1,q_2,q_3,qФ)
F: Final State

Transition Matrix

		f
		a	b
ε	p₀	p₁	qФ
a	p₁	p₂	qФ
ab	p₂	qФ	p₃
abb	p₃	p₃	p₃
	p₄	qФ	qФ

Transition Graph

3. Construct finite state automation (DFA) that starts with 'aba'.

Solution :
Σ: inputs = {a, b}
q₀ = initial state
q₁ = string starts with a
q₂ = string starts with ab
q₃ = string starts with aba

Q: set of all states (q_0,q_1,q_2,q_3,qФ)
F: Final State

Transition Matrix

		f
		a	b
ε	p₀	p₁	qФ
a	p₁	qФ	p₂
ab	p₂	p₃	qФ
abb	p₃	p₃	p₃
	p₄	qФ	qФ

Transition Graph

4. Construct finite state automation (DFA) that starts with ''.

Solution :
Σ: inputs = {a, b}
q₀ = initial state
q₁ = string starts with a
q₂ = string starts with aa
q₃ = string starts with aab
q₄ = string starts with aabb

Q: set of all states (q_0,q_1,q_2,q_3,q_4,qФ)
F: Final State

Transition Matrix