Theory Of Computation

Section B

Arden’s Theorem

In order to find out a regular expression of a Finite Automaton, we use Arden’s Theorem

along with the properties of regular expressions.

Statement:

Let P and Q be two regular expressions.

If P does not contain null string, then R = Q + RP has a unique solution that is R

= QP*

Proof:

R = Q + (Q + RP)P [After putting the value R = Q + RP]

= Q + QP + RPP

When we put the value of R recursively again and again, we get the following equation:

R = Q + QP + QP2 + QP3.....

R = Q (є + P + P2 + P3 + .... )

R = QP* [As P* represents (є + P + P2 + P3 + ....) ]

Hence, proved.

Assumptions for Applying Arden’s Theorem:

1. The transition diagram must not have NULL transitions

2. It must have only one initial state

Method

Step 1: Create equations as the following form for all the states of the DFA having

n states with initial state q1.

q1 = q1R11 + q2R21 + ... + qnRn1 + є

q2 = q1R12 + q2R22 + ... + qnRn2

................................

.................................

.................................

qn = q1R1n + q2R2n + ... + qnRnn

Rij represents the set of labels of edges from qi to qj, if no such edge exists, then Rij = Ø

Step 2: Solve these equations to get the equation for the final state in terms of Rij

Problem

Construct a regular expression corresponding to the automata given below:

Solution

Here the initial state is q2 and the final state is q1.

The equations for the three states q1, q2, and q3 are as follows:

q1 = q1a + q3a + є (є move is because q1 is the initial state0

q2 = q1b + q2b + q3b

q3 = q2a

Now, we will solve these three equations:

q2 = q1b + q2b + q3b

= q1b + q2b + (q2a)b (Substituting value of q3)

= q1b + q2(b + ab)

= q1b (b + ab)* (Applying Arden’s Theorem)

q1 = q1a + q3a + є

= q1a + q2aa + є (Substituting value of q3)

= q1a + q1b(b + ab*)aa + є (Substituting value of q2)

= q1(a + b(b + ab)*aa) + є

= є (a+ b(b + ab)*aa)*

= (a + b(b + ab)*aa)*

Hence, the regular expression is (a + b(b + ab)*aa)*.

Theory Of Computation

Section B

Identities Related to Regular Expressions

Given R, P, L, Q as regular expressions, the following identities hold:

1. Ø* = ε

2. ε* = ε

3. RR* = R*R

4. R*R* = R*

5. (R*)* = R*

6. RR* = R*R

7. (PQ)*P =P(QP)*

8. (a+b)* = (a*b*)* = (a*+b*)* = (a+b*)* = a*(ba*)*

9. R + Ø = Ø + R = R (The identity for union)

10. Rε = εR = R (The identity for concatenation)

11. ØL = LØ = Ø (The annihilator for concatenation)

12. R + R = R (Idempotent law)

13. L (M + N) = LM + LN (Left distributive law)

14. (M + N) L = LM + LN (Right distributive law)

15. ε + RR* = ε + R*R = R*

Theoy Of Computation

Section B

Regular Set.

Any set that represents the value of the Regular Expression is called a Regular Set.

Properties of Regular Sets

Property 1. The union of two regular set is regular.

Proof:

Let us take two regular expressions

RE1 = a(aa)* and RE2 = (aa)*

So, L1= {a, aaa, aaaaa,.....} (Strings of odd length excluding Null)

and L2={ ε, aa, aaaa, aaaaaa,.......} (Strings of even length including Null)

L1 ∪ L2 = { ε, a, aa, aaa, aaaa, aaaaa, aaaaaa,.......}

(Strings of all possible lengths including Null)

RE (L1 ∪ L2) = a* (which is a regular expression itself)

Hence, proved.

Property 2. The intersection of two regular set is regular.

Proof:

Let us take two regular expressions

RE1 = a(a*) and RE2 = (aa)*

So, L1 = { a,aa, aaa, aaaa, ....} (Strings of all possible lengths excluding Null)

L2 ={ ε, aa, aaaa, aaaaaa,.......} (Strings of even length including Null)

L1 ∩ L2 = { aa, aaaa, aaaaaa,.......} (Strings of even length excluding Null)

RE (L1 ∩ L2) = aa(aa)* which is a regular expression itself.

Hence, proved.

Property 3. The complement of a regular set is regular.

Proof:

Let us take a regular expression:

RE = (aa)*

So, L = {ε, aa, aaaa, aaaaaa, .......} (Strings of even length including Null)

Complement of L is all the strings that is not in L.

So, L’ = {a, aaa, aaaaa, .....} (Strings of odd length excluding Null)

RE (L’) = a(aa)* which is a regular expression itself.

Hence, proved.

Property 4. The difference of two regular set is regular.

Proof:

Let us take two regular expressions:

RE1 = a (a*) and RE2 = (aa)*

So, L1= {a,aa, aaa, aaaa, ....} (Strings of all possible lengths excluding Null)

L2 = { ε, aa, aaaa, aaaaaa,.......} (Strings of even length including Null)

L1 – L2 = {a, aaa, aaaaa, aaaaaaa, ....}

(Strings of all odd lengths excluding Null)

RE (L1 – L2) = a (aa)* which is a regular expression.

Hence, proved.

Property 5. The reversal of a regular set is regular.

Proof:

We have to prove L

R is also regular if L is a regular set.

Let, L= {01, 10, 11, 10}

RE (L)= 01 + 10 + 11 + 10

LR= {10, 01, 11, 01}

RE (LR)= 01+ 10+ 11+10 which is regular

Hence, proved.

Property 6. The closure of a regular set is regular.

Proof:

If L = {a, aaa, aaaaa, .......} (Strings of odd length excluding Null)

i.e., RE (L) = a (aa)*

L*= {a, aa, aaa, aaaa , aaaaa,...............} (Strings of all lengths excluding Null)

RE (L*) = a (a)*

Hence, proved.

Property 7. The concatenation of two regular sets is regular.

Proof:

Let RE1 = (0+1)*0 and RE2 = 01(0+1)*

Here, L1 = {0, 00, 10, 000, 010, ......} (Set of strings ending in 0)

and L2 = {01, 010,011,.....} (Set of strings beginning with 01)

Then, L1 L2 = {001,0010,0011,0001,00010,00011,1001,10010,.............}

Set of strings containing 001 as a substring which can be represented by an RE:

(0+1)*001(0+1)*

Hence, proved.

Theory Of Computation

Section B

Regular Expression

A Regular Expression can be recursively defined as follows:

1. ε is a Regular Expression indicates the language containing an empty string. (L (ε)

= {ε})

2. φ is a Regular Expression denoting an empty language. (L (φ) = { })

3. x is a Regular Expression where L={x}

4. If X is a Regular Expression denoting the language L(X) and Y is a Regular

Expression denoting the language L(Y), then

(a) X + Y is a Regular Expression corresponding to the language L(X) U L(Y)

where L(X+Y) = L(X) U L(Y).

(b) X . Y is a Regular Expression corresponding to the language L(X) . L(Y)

where L(X.Y)= L(X) . L(Y)

(c) R* is a Regular Expression corresponding to the language L(R*) where

L(R*) = (L(R))*

5. If we apply any of the rules several times from 1 to 5, they are Regular Expressions.

Some RE Examples

Theory Of Computation

 Section A

Finite Automata with Null Moves(NFA-ε)R

A Finite Automaton with null moves (FA-ε) does transit not only after giving input from

the alphabet set but also without any input symbol. This transition without input is called

a null move.

An NFA-ε is represented formally by a 5-tuple (Q, Σ, δ, q0, F), consisting of

Q : a finite set of states

Σ : a finite set of input symbols

δ : a transition function δ : Q × (Σ ∪ {ε}) → 2Q

q0 : an initial state q0 ∈ Q

F: a set of final state/states of Q (F⊆Q).

The above (FA-ε) accepts a string set: {0, 1, 01}

Removal of Null Moves from Finite Automata

If in an NDFA, there is ε-move between vertex X to vertex Y, we can remove it using the

following steps:

1. Find all the outgoing edges from Y.

2. Copy all these edges starting from X without changing the edge labels.

3. If X is an initial state, make Y also an initial state.

4. If Y is a final state, make X also a final state.

Problem

Convert the following NFA-ε to NFA without Null move.

Solution

Step 1:

Here the ε transition is between q1 and q2, so let q1 is X and qf is Y.

Here the outgoing edges from qf is to qf for inputs 0 and 1.

Step 2:

Now we will Copy all these edges from q1 without changing the edges from qf and

get the following FA:

Step 3:

Here q1 is an initial state, so we make qf also an initial state.

So the FA becomes -

Step 4:

Here qf is a final state, so we make q1 also a final state.

So the FA becomes -

Theory Of Computation

Section A

Mealy Machine to Moore Machine

Algorithm 5:

Input: Mealy Machine

Output: Moore Machine

Step 1 Calculate the number of different outputs for each state (Qi) that are     available in the state table of the Mealy machine.

Step2 If all the outputs of Q are same,copy state Qi.If it has n distinct outputs,break Qi into n states as Qin where n=0, 1,2.......

Step 3 If the output of the initial state is 1, insert a new initial state at the beginning which gives 0 output.

Example

Let us consider the following Mealy Machine:

Here, states ‘a’ and ‘d’ give only 1 and 0 outputs respectively,so we retain states ‘a’ and ‘d’. But states ‘b’ and ‘c’ produce different outputs (1 and 0).So, we divide b into b 0 ,b1 and c into c0,c1.

Hello Reader,

So this is my first post on this blog.
I am currently working as a Lecturer-cum-Developer in Hiet Shahpur.
The idea to start this blog came to me after analyzing the requirement of particularized notes and lab manuals required by students. So now I will try to post the notes and lab manuals for the students so that they can easily access things on a single blog and they don't have to get confused in online traffic to find the real content.

Theory Of Computation

Section A

Mealy Machine vs. Moore Machine

The following table highlights the points that differentiate a Mealy Machine from a Moore Machine.

Theory Of Computation

Section A

Moore Machine

Moore machine is an FSM whose outputs depend on only the present state.A Moore machine can be described by a 6 tuple(Q, Σ, O, δ,X,q0)where:

• Q is a finite set of states.
• Σ is a finite set of symbols called the input alphabet.
• O is a finite set of symbols called the output alphabet.
• δ is the input transition function where δ: Q × Σ→Q
• X is the output transition function where X: Q→O
• q0 is the initial state from where any input is processed (q0∈Q).

The state table of a Moore Machine is shown below–

The state diagram of the above Moore Machine is: