[go: up one dir, main page]
Scribd
Upload
88 views8 pages

Deterministic - Finite - Automata

This document defines and provides examples of deterministic finite automata (DFA). It states that a DFA is a 5-tuple consisting of a finite set of states, a finite set of input symbols, an initial state, final or accepting states, and a transition function. The transition function uniquely determines the next state based on the current state and input symbol. A DFA can be represented graphically using a state diagram with states as vertices and labeled transitions as arcs. An example DFA is provided that accepts all strings starting with 0.

Uploaded by

MUZAMMIL IBRAHMI 20BCE11083
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
88 views8 pages

Deterministic - Finite - Automata

This document defines and provides examples of deterministic finite automata (DFA). It states that a DFA is a 5-tuple consisting of a finite set of states, a finite set of input symbols, an initial state, final or accepting states, and a transition function. The transition function uniquely determines the next state based on the current state and input symbol. A DFA can be represented graphically using a state diagram with states as vertices and labeled transitions as arcs. An example DFA is provided that accepts all strings starting with 0.

Uploaded by

MUZAMMIL IBRAHMI 20BCE11083
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 8

DETERMINISTIC​

FINITE​
AUTOMATA​

VIT BHOPAL UNIVERSITY


TEAM MEMBERS

PREET SHARAN
20BAI10065

PRITHVI KAUSHIK SHARMA MD MUZAMMIL IBRAHMI


20BCE10675 20BCE11083

2
DEFINATION

DFA refers to deterministic finite automata. Deterministic refers to the uniqueness of


the computation. The finite automata are called deterministic finite automata if the
machine is read an input string one symbol at a time.
In DFA, there is only one path for specific input from the current state to the next
state.
DFA does not accept the null move, i.e., the DFA cannot change state without any
input character.
DFA can contain multiple final states. It is used in Lexical Analysis in Compiler.

3
A DFA is a collection of 5-tuples same as we described in the definition of FA.​
1. Q: finite set of states ​
2. ∑: finite set of the input symbol ​
3. q0: initial state ​
4. F: final state ​
5. δ: Transition function ​
​

Graphical Representation of DFA


A DFA can be represented by digraphs called state diagram. In which:


1. The state is represented by vertices.
2. The arc labeled with an input character show the transitions.
3. The initial state is marked with an arrow.
4. The final state is denoted by a double circle.

Graphical Representation of DFA

Example 1:

Q = {q0, q1, q2}


∑ = {0, 1}
q0 = {q0}
F = {q2}

Graphical Representation of DFA


Example 2:
DFA with ∑ = {0, 1} accepts all starting with 0.

Explanation:
In the above diagram, we can see that on given 0 as input to DFA in state q0 the DFA
changes state to q1 and always go to final state q1 on starting input 0. It can accept
00, 01, 000, 001....etc. It can't accept any string which starts with 1, because it will
never go to final state on a string starting with 1.
THANK YOU

You might also like