Deterministic Push down Automata (DPDA)

“Deterministic Push down Automata” (DPDA):

Formal definition:
A PDA M can be defined as a 7-tuple:
M = (Q,Σ,Γ,q0,Z0,A,δ) where
 Q is a finite set of states
 Σ is a finite set of the input alphabet
 Γ is a finite set of the stack alphabet
 q0 is the start state, an element of Q
 Z0 is the initial stack symbol, an element of Γ
 A is the set of final states, a subset of Q
 δ is a finite transition relation (Q x (Σ U {Λ} x Γ ) ----> the set of finite subsets of (Q x Γ* )

Non Deterministic Finite Automata (NFA)-continued

For every NFA a deterministic finite state machine (DFA) can be found that accepts the same language. Therefore it is possible to convert an existing NFA into a DFA for the purpose of implementing a (perhaps) simpler machine. This can be performed using the power set construction which may lead to an exponential rise in the number of necessary states.

NFA is very important for depth knowledge of Automata. You will see that almost everything in Automata Theory is related to NFA.
See you later..

Deterministic Finite Automata (DFA)

DFAs are equivalent in computing power to NFAs (nondeterministic finite automata).On the other hand, DFAs are of strictly limited power in the languages they can recognize — many simple languages, including any problem that requires more than constant space to solve, cannot be recognized by a DFA.
The classical example of a simply described language that no DFA can recognize is the language consisting of strings of the form anbn — some finite number of a's, followed by an equal number of b's. It can be shown that no DFA can have enough states to recognize such a language.
See you later with our next post….

Formal Definition of Deterministic Finite State Machine (DFA):

Formal Definition of Deterministic Finite State Machine (DFA):

A DFA is a 5-tuple, (S, Σ, T, s, A), consisting of

 a finite set of states (S)
 a finite set called the alphabet (Σ)
 a transition function (T : S × Σ → S)
 a start state (s ∈ S)
 a set of accept states (A ⊆ S)

Given an DFA M.
Given a string w.
There is at most one computation path of M with input w.
M accepts w if that computation path ends in a final state.

Automata Step by Step

Now we also need definition of “regular grammar”

Regular Grammars:

Regular grammars describe exactly all regular languages and are in that sense equivalent to finite state automata and regular expressions. Moreover, the right regular grammars by themselves are also equivalent to the regular languages, as are the left regular grammars.

Every regular grammar is a context-free grammar. Every context-free grammar can be easily rewritten into a form in which only a combination of left regular and right regular rules is used. Therefore, such grammars can express all context-free languages. Regular grammars, which use either left-regular or right-regular rules but not both, can only express a smaller set of languages, called the regular languages. In that sense they are equivalent with finite state automata and regular expressions.

What is a regular language? It is important to understand “regular language” for better understanding of above definitions. We will discuss it in our next post..