Finite automata and regular languages: theory

Among the different formal languages which occur naturally in the theory of automata and phrase structure grammars; regular languages are the easiest and arguably the most helpful. They are globally employed in text searching applications and they emerge as the significant components of practically all the formal notations made by computer science, like those parts of programming languages which can be processed by the lexical analysis. The Regular languages can be stated in three distinct ways: as languages approved by deterministic finite automata (or DFA), by non-deterministic finite automata (or NFA) and by regular expressions (or RE). Each of such formalisms sheds light on various properties of regular languages. The major goal of this section is to exhibit the equivalence of DFAs, NFAs and regular expressions, employing the cyclic reduction shown below, where X ≤ Y signifies ‘whatever can be stated by X, can as well be stated by Y’. As NFAs is a generalization of DFAs, represented by set inclusion ⊃, it is obvious that they are at least as powerful as DFAs -the interesting comparisons are such indicated by “≤”. From equivalence of such distinct models of computation, all the main properties of regular languages follow eagerly.

Varieties of automata: concepts, definitions and terminology

Notation: Alphabet A, example: A = {0, 1...}. Kleene star A* = {w | w = a1 a2 ... am, m ≥ 0, ai ∈ A}.

A+ = AA*.  Null string ε. Empty set {} or Ø.

“Language” L ⊆ A*. Set S = {s, s’... s0, s1...}. Cardinality |S|. Power set 2S. “¬” not or complement.

Deterministic Finite Automaton (FA, DFA) M = (S, A, f, s0, F)

Set of states S, alphabet A and transition function f: S x A -> S, initial state s0, accepting or final states F ⊆ S

Extend f from the S x A -> S to f: S x A* -> S as follows: f(s, ε) = s, f(s, wa) = f( f(s, w), a) for w ∈ Α∗

Df: M accepts w ∈ A* if and only if f(s0, w) ∈ F. Set L ⊆ A* approved by M: L(M)  = {w |  f(s0, w) ∈ F}.

Non-deterministic Finite Automaton (NFA) with ε-transitions: f: S x (A ∪ {ε}) -> 2S.

Special case: NFA with no ε-transitions:

f: S x A -> 2S .

Extend f: S x A* -> 2S:  f(s, ε) = ε-hull of s = all the states reachable from s through ε-transitions (comprising s);

f(s, wa) =  ∪ f(s’, a)  for s’ ∈ f(s, w).

Extend f further f: 2S x A* -> 2S as follows: f(s1, .., sk, a) = ∪ f(si, a) for i = 1, .., k.

Df: M accepts the w ∈ A* if and only if f(s0, w) ∩ F ≠ {}. Note: w is accepted if and only if ∃ some w-path from s0 fo F.

Set L ⊆ A* accepted by M: L(M) = {w |  f(s0, w) ∩ F ≠ {}}.

The operation of non-deterministic machine can be interpreted in two equivalent manners:

A) Oracle: For any given word w, when there is any sequence of transitions which leads to an accepting state, the machine will magically find out it, like a sleep walker, ignoring all the paths which lead to a rejecting state.

B) Concurrent computation: The machine spawns numerous copies of itself, each one tracing its own root-to-leaf path of tree of all the possible choices. When any copy reaches the accepting state, it broadcasts the success.

Non-determinism outcomes an exponential rise in computing power!

Df: Two FAs (of any kind) are equivalent if and only if they accept similar language.

Latest technology based Theory of Computation Online Tutoring Assistance

Tutors, at the www.tutorsglobe.com, take pledge to provide full satisfaction and assurance in Theory of Computation help via online tutoring. Students are getting 100% satisfaction by online tutors across the globe. Here you can get homework help for Theory of Computation, project ideas and tutorials. We provide email based Theory of Computation help. You can join us to ask queries 24x7 with live, experienced and qualified online tutors specialized in Theory of Computation. Through Online Tutoring, you would be able to complete your homework or assignments at your home. Tutors at the TutorsGlobe are committed to provide the best quality online tutoring assistance for Theory of Computation Homework help and assignment help services. They use their experience, as they have solved thousands of the Theory of Computation assignments, which may help you to solve your complex issues of Theory of Computation. TutorsGlobe assure for the best quality compliance to your homework. Compromise with quality is not in our dictionary. If we feel that we are not able to provide the homework help as per the deadline or given instruction by the student, we refund the money of the student without any delay.