Regular Expressions and Finite Automata

Finite Automaton

A Finite State Machine (FSM) or finite state automaton is an abstract machine used in the study of computation and language that has only a finite, constant amount of memory.

Types of Finite Automaton:

Deterministic Finite Automata (DFA)
Non-Deterministic Finite Automata (NFA or NDFA)
NFA with Epsilon moves (epsilon-NFA)

Description of Finite Automaton

A finite automaton is defined as 5-tuples (Q, Σ, δ, q₀, F). where, Q is finite non-empty set of states, Σ is finite non-empty set of input d alphabets, δ is transition function which maps Q × Σ into Q, q₀ is initial state and q₀ ∈ Q, F is set of final states and F ⊆ Q.

For DFA: Q × Σ → Q
For NFA: Q × Σ → 2^Q

Transition Diagrams

A transition diagram is a finite directed labelled graph in which each vertex represents a state and directed edges indicate the transition from one state to another. Edges are labelled with input/output. In this, the initial state is represented by a circle with an arrow towards it, the final state is represented by two concentric circles and intermediate states are represented by just a circle.

Example: Consider the following DFA.

In the given transition diagram, vertex A is the initial state of the finite automata and C is the final state.

Transition Table

Transition table is the tabular representation of transition system. In this representation, initial (start) state is represented by an arrow towards it and a final state is represented by a circle or prefixed with star symbol. Following transition table is equivalent to the above given transition diagram.

(Notations: → : initial state; *: final state)

Acceptability of a String by Finite Automata

A string ω is accepted by a finite automaton, M = (Q, Σ, δ, q₀, F), if δ(q₀, ω) = F, where q₀ is initial (start) state and F is the final state. For every input symbol of string it takes one transition and starts with initial state and reaches final state by reading the complete string.

Transition Function

It takes two arguments i.e., a state and an input symbol. δ(q, a) is the transition function for the DFA (Deterministic Finite Automata) which is at the state q and when it receives the input a, DFA will move to the next state.

Extended Transition Function

It takes two arguments a state and an input string.

δ^*(q, ω) = δ(δ(q, x), a)

where, ω is a string i.e., ω = xa, in which a is a single word and x is remaining string except the last symbol.

Equivalence of DFA and NDFA

In contrast to the NFA (NDFA), the Deterministic Finite Automata (DFA) has

No ε-transition (null transition).
For every (q, a) with q ∈ Q and a ∈ Σ at most one successor state.
Deterministic finite automata can simulate the behaviour of NFA by increasing the number of states.
In Deterministic Finite Automata (DFA), for each state, there is at most one transition for each possible input.
In non-deterministic finite automata, there can be more than one transition from a given state for a given possible input.
If a language L is accepted by an NFA, then there is a DFA that accepts L.
All DFA are NDFA, but not all NFA are DFA.
All NDFA and DFA have the same power.
Processing of an input string is more time consuming when NFA is used and less time consuming when DFA is used.

Finite Automata with Output Capabilities

There are two types of machines: Moore machine and Mealy machine.

Moore Machine

It is a finite automata in which output is associated with each state.

Moore machine is defined as 6-tuples (Q, Σ, Δ, δ, λ, q₀)

where, Q is finite non-empty set of states.

Σ is set of input symbols.
Δ is output alphabet.
δ is transition function which maps δ(Σ × Q) → Q.
λ is output function which maps Q into Δ.
q₀ is initial state.

Mealy Machine

It is a finite automata in which the output depends upon both the present input and present state. Mealy machine is also a 6-tuple (Q, Σ, Δ, δ, λ, q₀), where all symbols except λ have the same meaning as in Moore machine. λ is the output function mapping Σ × Q into Δ.

Regular Expression

Regular expressions mean to represent certain sets of strings in some algebraic fashion. A regular expression over the alphabet Σ is defined as follows

ϕ is a regular expression corresponding to the empty language ϕ.
ε is a regular expression corresponding to the language {ε}.
For each symbol a ∈Σ a is a regular expression corresponding to the language {a}.

Regular Language

The languages accepted by FA are regular languages and these languages are easily described by simple expressions called regular expressions.

For any regular expression r and s over Σ corresponding to the languages L_r and L_srespectively, each of the following is a regular expression corresponding to the language indicated.

(rs) corresponding to the language L_rL_s
(r + s) corresponding to the language L_r ∪ L_s
r^* corresponding to the language L_r.Some examples of regular expression are
1. L (01) = {0, 1}
2. L (01 + 0) = {01, 0}
3. L (0 (1+ 0)) = {01, 00}
4. L (0^*) = {ε, 0, 00, 000, …}
5. L ((0 + 10)^* (ε + 1)) = all strings of 0’s and 1’s without two consecutive 1’s.
If L₁ and L₂ are regular languages in Σ^*, then L₁ ∪ L₂, L₁ ∩ L₂, L₁ – L₂ and L₁(complement of L₁), are all regular languages.
Pumping lemma is a useful tool to prove that a certain language is not regular.

Regular Set

A set represented by a regular expression is called regular set e.g., If Σ = {a, b} is an alphabet, then

Different Regular Sets and their Expressions

Identities for Regular Expressions

The following points are the some identities for regular expressions.

ϕ + R = R + ϕ = R
ε R = R ε = R
R + R = R, where R is the regular expression.
(R^*)^* = R^* ϕR = Rϕ = ϕ
ε^* = ε and ϕ^* = ε
RR^* = R^*R = R⁺
R^*R^* = R^*
(P + Q)^* = (P^*Q^*)^* = (P^* + Q^*)^*, where P and Q are regular expressions.
R (P + Q) = RP + RQ and (P + Q)R = PR + QR
P(QP)^* = (PQ)^*P

Arden’s Theorem

If P and Q are two expressions over an alphabet Σ such that P does not contain ε, then the following equation R = Q + RP.
The above equation has a unique solution i.e., R = QP^*. Arden’s theorem is used to determine the regular expression represented by a transition diagram.
The following points are assumed regarding transition diagrams
The transition system does not have any
It has only one initial (starting) stage.

Properties of Regular Language

Regular languages are closed under following properties

Union
Concatenation
Kleene closure
Complementation
Transpose
Intersection

Regards
Amrut Jagdish Gupta

Undecidability

Amu_Ke_Fundye Undecidability Decidable Problem If there is a Turing machine that decides the problem, called as Decidable problem. A decision problem that can be solved by an algorithm that halts on all inputs in a finite number of steps. A problem is decidable, if there is an algorithm that can answer either yes or no. A language for which membership can be decided by an algorithm that halts on all inputs in a finite number of steps. Decidable problem is also called as totally decidable problem, algorithmically solvable, recursively solvable. Undecidable Problem A problem that cannot be solved for all cases by any algorithm whatsoever. Equivalent Language cannot be recognized by a Turing machine that halts for all inputs. The following problems are undecidable problems: Halting Problem: A halting problem is undecidable problem. There is no general method or algorithm which can solve the halting problem for all possible inputs. Emptyness Problem:...

Amu_Ke_Fundye

Search This Blog