Automata theory (Discrete Structure Note Introduction)
4 years agoThe Term "Automata" is derived from the Greek word "αὐτόματα" which means "self-acting". in general, Automata is an abstract computing device that follows a predetermined sequence of operations automatically.
Thus Automata is a special kind of machine that is closely linked to a particular type of language. In this chapter, we will discuss finite-state automata and their languages.
Sequential Circuits and Finite State Machine
Alphabet
An alphabet is any finite set of symbols.
Example: S={a, b, c, d} is an alphabet set where 'a', 'b', 'c', and 'd' are symbols.
String
A string is a finite set of symbols taken from S.
Example: 'cabcad' is a string on the alphabe set S={a,b,c,d}
Length of String
Length of string is the number of symbols present in a string. (Denoted by |s|.
Example:
- If S='cabcad', |s|=6
- If |S| = 0, it is called an empty string Denoted by λ or ε
Finite State Automata
FAS is a simple model of computation. It has very limited memory. FSA can be classified into two broad categories: DFA and NFA.
- Given the current state, we will know what the next state will be
- It has only one unique next state
- It has no choices or randomness
- It is simple and easy to design
A deterministic finite-state machine is an abstract model with a primitive internal memory with four basic components.
Q: set of all state
Σ: inputs
δ: transition function from Q × Σ
q0 : start state / initial states
Graphical representation of DFA
A DFA is represented by digraphs called state diagrams. in a state diagram
- The verities represent the states.
- The arcs labeled with an input alphabet show the transitions.
- The initial state is denoted by an empty single incoming arrow.
- The finite state is indicated by double circles.
