The 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.

DFA = Deterministic Finite Automata

NFA = Non-deterministic Finite Automata

DFA is deterministic finite automata. It has the following features.

- 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.

177