### Automata Theory is the study of abstract machines and automata as well as the study of computational problems which can be solved using them.

### The word automata comes from the greek word which means "self-making".

### Automata Plays a major important role in Theory of Computation, Artificial Intelligence,Compiler Construction,Parsing,Formal Verification.

## Classes of Automata:

### An automaton is a construct made of states which designed to determine if the input should be accepted or rejected.

## Formal definition

### Q is a finite set of

*states*.### Σ is a finite set of

*symbols*, called the*alphabet*of the automaton.### δ is the

**transition function**, that is, δ: Q × Σ → Q.### q

_{0}is the*start state*, that is, the state of the automaton before any input has been processed, where q_{0}∈ Q.### F is a set of states of Q (i.e. F⊆Q) called

**accept states**.

#### Automaton

### definition of finite state automata

### A deterministic finite **automaton** is represented formally by a 5-tuple **<Q, Σ,δ,q**_{0},F>, where:

_{0},F>

- Input word
- An automaton reads a finite string of symbols a
_{1},a_{2},...., a_{n}, where a_{i}∈ Σ, which is called an*input word*. The set of all words is denoted by Σ*. - Run
- A sequence of states q
_{0},q_{1},q_{2},...., q_{n}, where q_{i}∈ Q such that q_{0}is the start state and q_{i}= δ(q_{i-1},a_{i}) for 0 < i ≤ n, is a*run*of the automaton on an input word w = a_{1},a_{2},...., a_{n}∈ Σ*. In other words, at first the automaton is at the start state q_{0}, and then the automaton reads symbols of the input word in sequence. When the automaton reads symbol a_{i}it jumps to state q_{i}= δ(q_{i-1},a_{i}). q_{n}is said to be the*final state*of the run.

- Accepting word
- A word w ∈ Σ* is accepted by the automaton if q
_{n}∈ F.

- Recognized language
- An automaton can recognize a formal language. The language L ⊆ Σ* recognized by an automaton is the set of all the words that are accepted by the automaton.

- Recognizable languages
- The recognizable languages are the set of languages that are recognized by some automaton. For the above definition of automata the recognizable languages are regular languages. For different definitions of automata, the recognizable languages are different.

## An example of a deterministic finite automaton that accepts only binary numbers that are multiples of 3. The state q0 is both the start state and an accept state. For example, the string "1001" leads to the state sequence q0, q1, q2, q1, q0, and is hence accepted.Please Follow the Video and Then go for the Code for Better Understanding.

```
dfa={0:{'0':0,'1':1},
1:{'0':2,'1':0},
2:{'0':1,'1':2}}
def accepts(delta,start,final,sigma):
state=start
for input in sigma:
state=dfa[state][input]
return state in final
print(accepts(dfa,0,{0},'1001'))
```

```
```

# Nondeterministic finite automaton:

## A nondeterministic finite automaton (NFA), or nondeterministic finite-state machine, does not need to obey DFA restrictions. In particular, every DFA is also an NFA. Sometimes the term NFA is used in a narrower sense, referring to an NFA that is not a DFA, but not in this article.

## NFA consumes a string of input symbols, one by one. In each step, whenever two or more transitions are applicable, it "clones" itself into appropriately many copies, each one following a different transition. If no transition is applicable, the current copy is in a dead end, and it "dies". If, after consuming the complete input, any of the copies is in an accept state, the input is accepted, else, it is rejected.

### An automatan is a construct made of states which designed to determine if the input should be accepted or rejected.

## Formal definition

### Q is a finite set of

*states*.### Σ is a finite set of

*symbols*, called the*alphabet*of the automaton.### δ is the

**transition function**, that is, δ: Q × Σ →P(Q).### q

_{0}is the*start state*, that is, the state of the automaton before any input has been processed, where q_{0}∈ Q.### F is a set of states of Q (i.e. F⊆Q) called

**accept states**.

#### Automaton

### definition of non deterministic finite state automata

### A Non Deterministic Finite Automaton is same as deterministic finite **automaton** is represented formally by a 5-tuple **<Q, Σ,δ,q**_{0},F>, where:

_{0},F>

## Here P(Q) denotes the Power set of Q

## Example:NFA which matches strings beginning with '1', ending with '1', and containing no consecutive '0's

## To perform this Operation Please install this module just type in CMD: pip install automata-lib

```
from automata.fa.nfa import NFA
nfa = NFA(
states={'q0', 'q1', 'q2'},
input_symbols={'1', '0'},
transitions={
'q0': {'1': {'q1'}},
# Use '' as the key name for empty string (lambda/epsilon) transitions
'q1': {'1': {'q1'}, '': {'q2'}},
'q2': {'0': {'q0'}}
},
initial_state='q0',
final_states={'q1'}
)
print(nfa.read_input('101'))
```

```
```

# PushDown Automaton:

### A pushdown automaton (PDA) is a type of automaton that employs a stack.Pushdown automata are used in theories about what can be computed by machines. They are more capable than finite-state machines but less capable than Turing machines. Deterministic pushdown automata can recognize all deterministic context-free languages while nondeterministic ones can recognize all context-free languages, with the former often used in parser design.A finite-state machine just looks at the input signal and the current state: it has no stack to work with. It chooses a new state, the result of following the transition. A **pushdown automaton (PDA)** differs from a finite state machine in two ways:- It can use the top of the stack to decide which transition to take.
- It can manipulate the stack as part of performing a transition.

A pushdown automaton reads a given input string from left to right. In each step, it chooses a transition by indexing a table by input symbol, current state, and the symbol at the top of the stack. A pushdown automaton can also manipulate the stack, as part of performing a transition. The manipulation can be to push a particular symbol to the top of the stack, or to pop off the top of the stack. The automaton can alternatively ignore the stack, and leave it as it is.Put together: Given an input symbol, current state, and stack symbol, the automaton can follow a transition to another state, and optionally manipulate (push or pop) the stack.Pushdown Automata is a finite automata with extra memory called stack which helps Pushdown automata to recognize Context Free Languages.

## A PDA is formally defined as a 7-tuple:

where

- Q is the set of states
- ∑is the set of input symbols
- Γ is the set of pushdown symbols (which can be pushed and popped from stack)
- q0 is the initial state
- Z is the initial pushdown symbol (which is initially present in stack)
- F is the set of final states
- δ is a transition function which maps Q x {Σ ∪ ∈} x Γ into Q x Γ*. In a given state, PDA will read input symbol and stack symbol (top of the stack) and move to a new state and change the symbol of stack.

## Example:DPDA which which matches zero or more '0's, followed by the same number of '1's (accepting by final state)

```
from automata.pda.dpda import DPDA
dpda = DPDA(
states={'q0', 'q1', 'q2', 'q3'},
input_symbols={'0', '1'},
stack_symbols={'0', '1'},
transitions={
'q0': {
'0': {'0': ('q1', ('1', '0'))} # transition pushes '1' to stack
},
'q1': {
'0': {'1': ('q1', ('1', '1'))},
'1': {'1': ('q2', '')} # transition pops from stack
},
'q2': {
'1': {'1': ('q2', '')},
'': {'0': ('q3', ('0',))} # transition does not change stack
}
},
initial_state='q0',
initial_stack_symbol='0',
final_states={'q3'},
acceptance_mode='final_state'
)
print(dpda.read_input('01'))
```

# Turing Machine:

### A Turing Machine is an accepting device which accepts the languages (recursively enumerable set) generated by type 0 grammars. It was invented in 1936 by Alan Turing. A Turing Machine (TM) is a mathematical model which consists of an infinite length tape divided into cells on which input is given. It consists of a head which reads the input tape. A state register stores the state of the Turing machine. After reading an input symbol, it is replaced with another symbol, its internal state is changed, and it moves from one cell to the right or left. If the TM reaches the final state, the input string is accepted, otherwise rejected.

### A TM can be formally described as a 7-tuple (Q,∑,Γ,δ,q0,B,F) where −
- Q is a finite set of states
- Γ is the tape alphabet
- ∑ is the input alphabet
- δ is a transition function; δ : Q × Γ → Q × Γ × {Left_shift, Right_shift}.
- q0 is the initial state
- B is the blank symbol
- F is the set of final states

## Example:DTM which matches all strings beginning with '0's, and followed by the same number of '1's

```
from automata.tm.dtm import DTM
dtm = DTM(
states={'q0', 'q1', 'q2', 'q3', 'q4'},
input_symbols={'0', '1'},
tape_symbols={'0', '1', 'x', 'y', '.'},
transitions={
'q0': {
'0': ('q1', 'x', 'R'),
'y': ('q3', 'y', 'R')
},
'q1': {
'0': ('q1', '0', 'R'),
'1': ('q2', 'y', 'L'),
'y': ('q1', 'y', 'R')
},
'q2': {
'0': ('q2', '0', 'L'),
'x': ('q0', 'x', 'R'),
'y': ('q2', 'y', 'L')
},
'q3': {
'y': ('q3', 'y', 'R'),
'.': ('q4', '.', 'R')
}
},
initial_state='q0',
blank_symbol='.',
final_states={'q4'}
)
print(dtm.read_input('0011') )
```

```
```