Info-Grade: Discrete Structure

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

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

Transition Graph

Automata theory (Discrete Structure Note)

Discrete Structure (Graph Theory | Walk, Path, Trial, Cycle and Circuit)

Graph Theory |Walk, Path, Trial, Cycle and Circuit in Graph|

Walk

Let G=(V, E) a Graph, then

A walk in G is a list W={u, e1, v1, e2, v2 ...... v} whose elements are alternatively vertices and degrees.

The vertices u and v are called its end-vertices.

The vertices v1, ........ are called inner vertices.

In a simple graph, walk can be denoted by sequence of vertices only.

Path

Let G=(V, E) be a Graph, then

A path in G is a walk with no repeated vertex and edges.

Trial

Let G=(V, E) be a Graph, then

A trial in G is a walk with no repeated edges.

Cycle

Let G=(V, E) be a Graph, then

A cycle in G is a closed path.

In a cycle, start and end vertex are same.

Circuit

Let G=(V, E) be a graph, then

A trial in G is a walk with no repeated edges. Now a closed trial in G is closed circuit.

Example: In the graph given below, construct walk, path, trial, cycle and circuit from a to e.

Graph

Solution Here,
1. Walk (Vertex and Edge can be repeated)

walk = {a, b, f, a, b, e}

2. Path (Vertex and Edge is not repeated)

path = {a, b, f, e}

3. Trial (Vertex can be repeated, Edges not repeated)

trial = {a, b, f, g, a, f, e}

4. Cycle (Vertex not repeated, Edge not repeated, close path)

cycle = {a, b, e, f, a}

5. Circuit (Vertex can be repeated, edge not repeated, close trial)

circuit = {a, f, b, e, f, g, a}

Finding Shortest Path in Graph (Dijkstra's Algorithm)

Dijkstra's algorithm is used to find the shortest path between source vertex (a) to destination vertex (b).

According to Dijkstra's algorithm, to find the shortest path from source vertex to destination vertex we need to follow the following steps.
Step 1: Remove all the loops
Step 2: Remove all parallel edges between two vertices except the one with least weight.
Step 3: Create the weight matrix table
i) Set 0 to the source vertex and infinite to the remaining vertices.
For all vertices, repeat (ii) and (iii)
ii) Mark the smallest unmarked value and mark that vertex.
iii) Find those vertices which are directly connected with marked vertex and update all.
Update value formula:
New Destination value = Minimum(Old destination value, Marked value + Edge weight)
Step 4: Perform backtrack
Some Examples:

1. Find shortest path from a to g.