AUTOMATA DEFINITIONS

 AUTOMATA DEFINITIONS

THIS SUBJECT IS FULLY BASED ON EXAMPLES, DEFINITIONS, GRAMMAR RULES, DIAGRAMS AND THEOREMS.

IMPORTANT DEFINITIONS: 

DFA: 

  A Deterministic Finite State Automaton (DFSA) is denoted by M and it is a set of 5-tuples i.e. M=(Q, Σ, δ, q₀, F) where,

* Q is a non-empty finite set of states

* Σ is a non-empty finite set of input symbols

*  q_{0 is the initial state or starting state. (q0 ∈ Q)}

* F is a non-empty finite set of final state. (F ⊆ Q).

* δ (pronounce delta) is the transition function. Q x Σ → Q.

δ(q,a) = p means, if  the automation is in state q and reading a symbol a, it goes to state p in the next instant, moving the pointer one cell to the right.

NDFA: 

  A Non-Deterministic Finite State Automaton (NFSA) is denoted by M and it is a set of 5-tuples i.e. M=(Q, Σ, δ, q₀, F) where,

* Q is a non-empty finite set of states

* Σ is a non-empty finite set of input symbols

*  q_{0 is the initial state or starting state. (q0 ∈ Q)}

* F is a non-empty finite set of final state. (F ⊆ Q).

* δ (pronounce delta) is the transition function. Q x Σ → 2^Q.

δ(q,a) = p means, if  the automation is in state q and reading a symbol a, it goes to state p in the next instant, moving the pointer one cell to the right.

δ(q,a) = p, q means, if  the automation is in state q and reading a symbol a, maybe it remains stay to state q in the next instant, does not moving the pointer Or, it goes to state p in the next instant, does not moving the pointer one cell to the right. That's why non-deterministic.

δ(q,ε) = p means, if  the automation is in state q and reading a symbol ε, it goes to state p in the next instant, moving the pointer one cell to the right. That's means NFSA permits empty string transitions.

REGULAR EXPRESSION:

    Let Σ be an alphabet. 

For each a in Σ, a is a regular expression representing the regular set {a}.

φ is a regular expression representing the empty set.

ε is a regular expression representing the set {ε}.

If r1 and r2 are regular expressions representing the regular sets R1 and R2 respectively, 

then r1 + r2 is a regular expression representing R1 ∪ R2. 

r1.r2 is a regular expression representing R1.R2. 

r∗1 is a regular expression representing R∗1. 

Any expression obtained from φ, ε, a(a ∈ Σ) using the above operations and 

parentheses where required is a regular expression. 

Example: (ab)∗abcd represent the regular set 

{(ab)ncd/n ≥ 1}