• Courses
• Data Structure
• ### Automata theory (Discrete Structure Note Introduction)

Posted on 2021-03-27

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

What is DFA?
DFA is deterministic finite automata. It has the following features.
1. Given the current state, we will know what the next state will be
2. It has only one unique next state
3. It has no choices or randomness
4. 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.

447

#### Recent MCQs

 History and Generation MCQ 1 MS-Excel Quick Tip 2 MS-Excel Quick Tip 1 MS-Word Quick Tip 3