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.

regular language-formal defnition continued

A regular language is a formal language (i.e., a possibly infinite set of finite sequences of symbols from a finite alphabet) that satisfies the following equivalent properties:
 it can be accepted by a deterministic finite state machine
 it can be accepted by a nondeterministic finite state machine
 it can be accepted by an alternating finite automaton
 it can be described by a regular expression
 it can be generated by a regular grammar
 it can be accepted by a read-only Turing machine
In next post, I will discuss formal definition of deterministic finite state machine (DFA). DFA is my Favorite topic.
I am sure you will also like it when we will discuss it in detail after completing all formal definitions.