4

Regular Expression

4.1 BASICS OF REGULAR EXPRESSION

Q. What is Regular Expression?

Ans. A regular expression can be defined as a language or string accepted by a finite automata.

We know that a finite automata consists of five touples {Q, Σ, δ, q₀, F}. Among them a Regular Expression is a string on Σ, i.e. it will consist only with input alphabets.

In short a Regular Expression is written as RE.

Q. Give some formal recursive definition of Regular Expression

Ans.

(i) Any terminals, i.e. the symbols belong to Σ are Regular Expression. Null string(Λ) and Null set(Φ) are also Regular Expression.

(ii) If P and Q are two Regular Expressions then the union of the two Regular Expressions denoted by P + Q is also a Regular Expression.

(iii) If P and Q are two Regular Expressions then their concatenation denoted by PQ is also a Regular Expression.

(iv) If P is a Regular Expression then the iteration (repetition or closure) denoted by P^* is also a Regular Expression.

(v) If P is a Regular Expression then (P) is a Regular Expression.

(vi) The expressions got by repeated application of the rules from (i) to (v) over Σ are also Regular Expression.

Q. Describe three basic operations on Regular Expression.

Ans. Three basic operations are Union, Concatenation and closure.

 

Operation of union on Regular Expression: If R₁ and R₂ are two Regular Expression s over Σ then L(R₁ R₂) is denoted by L(R₁ + R₂).

L(R₁ R₂) is a string from R₁ or a string from R₂.

L(R₁ + R₂) = L(R₁) L(R₂).

 

Operation of Concatenation on Regular Expression: If R₁ and R₂ are two Regular Expression s over Σ then L(R₁ R₂) is denoted by L(R₁R₂).

L(R₁ R₂) is a string from R₁ followed by a string from R₂.

L(R₁R₂) = L(R₁)L(R₂).

 

Operation of Closure on Regular Expression: If R₁ and R₂ are two Regular Expressions over Σ then L(R^*) is a string obtained by concatenating n elements for n ≥ 0.

Q. Define Kleene's Closure with example. What is the difference with Closure?

Ans.

Kleene's Closure: It is defined as a set of all strings including null (Λ) obtained from the alphabets of the set Σ. It is denoted as Σ^*.

If

If Σ = {0, 1}, then Σ^* = {Λ, 0, 1, 01, 00, 11, 010, 011, 100 }.

 

Difference

(i) Closure is nothing but iteration of 0 to ∞ times, but Kleene's Closure is set including Λ.

(ii) Closure is applied on Regular Expression, but Kleene's Closure is applied on Σ

(iii) If R = 01, then Closure on R denoted by R^* are Λ, 01, 0101, 010101 ,…, etc., i.e. iteration of the same string 01.

If Σ = {0, 1} then Kleene's Closure denoted

by Σ^* = {Λ, 0, 1, 01, 00, 11, 010, 011, 100,…}, i.e. set of any combinations of 0 and 1 including Λ.

Q. Describe the following REs in English language.

Ans.

(i) The strings that we get from the Regular Expression 10*1 are {11, 101, 1001, 10001,…}. From the set we can conclude that the strings that are generated from the Regular Expression s are beginning with 1 and ending with 1. In between 1 and 1 there are any numbers of 0.

So we can describe in English like this:

Set of all strings, beginning and ending with 1 with any number of 0 in between two 1.

(ii) The strings that we get from the Regular Expression a^*b^* are a^*.b^*, i.e. {Λ, a, aa, aaa,…}.{Λ, b, bb, bbb,…} = {Λ, a, b, aa, bb, ab, abb, aab,…} from the set we can conclude that the strings that are generated from the Regular Expression, contain any number of ‘a’ followed by any number of ‘b’,

so we can describe in English like this:

Set of all strings of ‘a’ and ‘b’ containing any number of ‘a’ followed by any number of ‘b’.

(iii) The strings that we get from the Regular Expression (ab)^* are {Λ, ab, abab, ababab,…}.

In English it can be said as:

Set of all string of a and b with equal number of a and b containing ‘ab’ as repetition.

(iv) (a^* + b^*) means any combination of a or any combination of b. The c^* means any combination of c, which is concatenated with (a^* + b^*).

In English it can be described as

Any combination of ‘a’ or any combination of ‘b’ followed by any combination of ‘c’.

(v) The strings that we get, from the Regular Expression (00)^*(11)^*1, are {1, 001, 111, 00111,…}. In the string there are always odd number of 1 and even number of 0.

In English it can be described as:

Set of all strings of ‘0’ and ‘1’ with even number 0 followed by odd number of 1.

Q. Construct Regular Expression from the description given below.

(i) A Regular Expression consists of any combination of a and b; beginning with a, and ending with b.

(ii) A language of any combination of a and b containing abb as a substring.

(iii) Regular Expression of a and b containing at least 2 ‘a’s.

(iv) Write Regular Expression for the language L = {aⁿb^m | where m + n is even}.

(v) A Regular Expression of a and b, having exactly one ‘a’.

Ans.

(i) The Regular Expression consists of any combination of a and b, i.e. (a + b)^*. But the Regular Expression starts with a and ends with b. In between a and b any combination of a and b occurs. So the Regular Expression is

L = a(a + b)^*b.

(ii) In the Regular Expression abb occurs as a substring. The R.E. consists of any combination of a and b. The substring abb may occur at the beginning, at the middle, or at the last. If abb occurs at the beginning then after abb there is any combination of a and b. If abb occurs at the middle then before and after abb there are any combination of a and b. If abb occurs at the last then before abb there is any combination of a and b.

So the Regular Expression is L = (a + b)^*abb(a + b)^*.

(iii) The expression consists of a and b and it contains atleast two a. There may be more than two a. So any combination of ‘a’ and ‘b’ can occur before the first ‘a’, before the second ‘a’, i.e. after the first ‘a’ and after the second ‘a’.

So the Regular Expression will be L = (a + b)^*a(a + b)^* a(a + b)^*

(iv) The Regular Expression consists of n number of ‘a’ followed by m number of ‘b’. However, m + n is always even. This is possible if

(a) m and n both are even or (b) m and n both are odd.
If m and n are both even then the expression will be (aa)^*(bb)^*.
If m and n are both odd then the expression will be (aa)^*a(bb)^*b
By combining these two the Regular Expression will be
L = (aa)^*(bb)^* + (aa)^*a(bb)^*b.

(v) In the Regular Expression there is exactly one ‘a’. Before and after a there is any combination of b.

   Hence the Regular Expression will be L = b*ab*.

Q. Mention the identities of Regular Expression.

Ans. We all know that by using two points one and only one straight line can be drawn. This statement is taken as a true and based on that the Geometry stands. This cannot be proved. This is taken as a universal truth. This type of statements is called Identities.

For Regular Expression there are also some identities.

Q. From the Identities of Regular Expression prove that
(1 + 100^*) + (1 + 100^*)(0 + 10^*)(0 + 10^*)^* = 10 (0 + 10^*)^*.

Ans. LHS

Q. From the Identities of Regular Expression prove that

Ans. Take 1^*(011)^* as P then the LHS becomes

Q. From the Identities of Regular Expression prove that

Ans.

4.2 ARDEN THEOREM

Q. State and prove Arden's theorem.

Ans.

Arden's Theorem:

Statement: Let P and Q be two Regular Expression s over Σ. If P does not contain Λ, then for the equation

R = Q + RP has a unique (one and only one) solution R = QP^*.

Proof:

Now point out the statements in Arden's Theorem in General form.

(i) P and Q are two Regular Expressions.

(ii) P does not contain Λ symbol.

(iii) R = Q + RP has a solution, i.e. R = QP^*

(iv) This solution is the one and only one solution of the equation.

If R = QP^* is a solution of the equation R = Q + RP then by putting the value of R in the equation we shall get the value ‘0’.

(Putting the value of R in the LHS we get)

So from here it is proved that R = QP^* is a solution of the equation R = Q + RP.

Now we have to prove that R = QP^* is the one and only one solution of the equation R = Q + RP.

As R = Q + RP, so put the value of R again and again in the RHS of the equation.

After several steps we shall get

Now let a string w belongs to R. If w is a Λ string then in which part the Λ will belong?

This string will belong to either in part or in RP^{n + 1} part. However, according to point number (ii) P does not contain Λ, so the string w does not belong to RP^{n + 1} . So it will obviously belong to which is nothing but QP^*. [(Λ + P + P + P³ + ---- Pⁿ ) is any combination of P including Λ].

As this string belongs only in one part so R and QP^* represents the same set. That means R = QP^* is the unique solution of the equation R = Q + RP.

Q. How Regular Expression can be constructed from Finite Automata by Algebraic Method using Arden's Theorem.

Ans.

There are some assumptions:

(i) In the transitional graph there will be no Λ-move.

(ii) In the Finite Automata there will be only one initial state.

For the Finite Automata given above there is no Λ-move. And it has only one initial state.

Now we have to construct equations for all the three states. There will be n number of equations if there are n-states.

For any Finite Automata these equations will be constructed in the following way.

<State Name> = Σ[<State Name from which inputs are coming>.<input>]

For the beginning state there is an arrow at the beginning coming from no state. Therefore, a Λ will be added with the equation of beginning state.

Then these equations have to be solved by the Identities of Regular Expression. The expression consists of only the input symbols of Σ, for the final state is the Regular Expression for the Finite Automata.

Q. Construct a Regular Expression from the given Finite Automata by Algebraic Method using Arden's Theorem

Ans.

For the above given Finite Automata the equations will be

Put the value of q₂ in equation no. (ii)

This equation is in the form R = Q + RP where R = q₁ , Q = q₀.0 and P = (1 + 0.0)

So the solution of the equation will be R = QP^*, i.e. q₁ = q₀.0. (1 + 0.0)*

Put the value q₂ = q₁.0 in equation no. (i).

We will get

q0 = q₀.1 + q₁.0.1 + Λ

Again put the value of q₁ in the above equation, we will get

This equation is in the form R = Q + RP, where R = q₀, Q = Λ and P = (1 + 0.(1 + 0.0)*.0.1). So the solution of the equation:

As q₂ is the final state of the Finite automata so all strings will halt on this state. So the Regular Expression will be [1 + 0.(1 + 0.0)^*.0.1]^*.0. (1 + 0.0)^*.0 accepting the Finite Automata.

Q. Construct a Regular Expression from the given Finite Automata by Algebraic Method using Arden's Theorem

Ans.

For the above given Finite Automata the equations will be

Solution:

Substituting the value of q₂ and q₃ in q₁ we get.

If q₁ is treated as R, Λ as Q and (01 + 10) as P then the equation will become R = Q + RP

The solution for the equation will be R = QP^*.

Therefore

As q₁ is the only final state so the string accepted by the Finite Automata is (01 + 10)^*

[We are seeing that we do not need the equation (iv), i.e. the equation for q₄ in the solution process. Here equation (iv) is redundant.]

Q. Construct a Regular Expression from the given Finite Automata by Algebraic Method using Arden's Theorem

Ans. For the given Finite Automata the equations:

Solution:

q₃ = q₂.a, replace this in equation (ii). The equation will become

q₂ = q₂.b + q₂a.b + q₁.b,

   = q₂(b + a.b) + q₁.b.

The equation is in the format of R = Q + RP, q₂[R] = q₂[R](b + a.b)[P] + q₁.b [Q].

The solution will be R = QP^* i.e. q₂ = q₁b.(b + ab)^*.

Replace the value of q₂ in equation (iii).

Replace the value of q₃ in equation (i),

The equation is in the format of R = Q + RP, q₁[R] = q₁[R].[a + b.(b + ab)^*.a.a][P] + Λ[Q]. The solution of the equation will be R = QP^*, i.e. q₁ = Λ[a + b.(b + ab)^*.a.a]^*,

i.e. q₁ = [a + b.(b + ab)^*.a.a]^* [According to ΛR = RΛ = R]

q₁ is the final state, so the Regular Expression accepting the Finite Automata is

[a + b.(b + ab)^*.a.a]^*.

4.3 CONSTRUCTION OF FINITE AUTOMATA EQUIVALENT TO A REGULAR EXPRESSION

Q. What is the process of construction of Finite Automata equivalent to a Regular Expression?

Ans. The Regular Expression is the language format of finite automata. There are two steps for making a finite automata from an Regular Expression.

Step I: From the given Regular Expression an equivalent transitional system (Finite Automata) with Λ move has to be constructed.

Step II: From the transitional system with Λ moves a DFA need to be constructed.

For constructing Step I again there are several steps.

(i) Take two states one is Beginning state and another is Final state. Make a transition from Beginning state to Final state and place the Regular Expression in between the beginning and final state.

(ii) If in the Regular Expression there is a ‘ + ’ (union) sign, then there are parallel paths between the two states.

(iii) If in the Regular Expression there is a ‘.’ (dot) sign, then one extra state will be added between the two states.

(iv) If in the Regular Expression there is a ‘*’ (closure) sign, then a loop will be added to the next state putting label Λ between the two states.

Q. Construct Finite Automata equivalent the Regular Expression.

Ans.

I. Two states are taken. One is beginning state and another is final state. The Regular Expression is placed between the two states with a transition from beginning state to final state.

II. In the Regular Expression there are two ‘.’ (Concatenation), between (a + b)^* and (aa + bb), and (aa + bb) and (a + b)^*, two extra states will be added between q₀ and q_f .

III. In aa and bb there is a ‘ + ’ (Union) sign. Therefore between q₁ and q₂ there will be parallel paths.

IV. There are two ‘*’ (Closure) signs between q₀ and q₁, and q₂ and q_f . So, loop with label a + b will be added to q₁ and q_f, making transitions between q₀, q₁ and q₂, q_f with label Λ.

V. Removing ‘ + ’ (Union) and ‘.’(Concatenation) the final Finite Automata with Λ transitions will be.

VI. Between q₀, q₁ and q₂, q_f there is a label Λ. It means from q₀ by getting no input it can reach to q₁, same thing is for q₂ and q_f. So q₀ and q₁ may be treated as same state, same for q₂ and q_f. The transitions from q₁ and q_f will be added with q₀ and q₂, respectively with same label.

By removing the Λ transactions the Finite Automata will be

Q. Construct Finite Automata equivalent to the Regular Expression.

Ans.

I.

II.

III.

IV.

V.

Q. Construct Finite Automata equivalent the Regular Expression.

Ans. Step I: Take a beginning state q₀ and a final state q_f .Between the beginning and final state place the Regular Expression.

Step II: Between ab and (aa + bb)(a + b)* there is a + sign, so there will be parallel edges between q₀ and q_f.

Step III: Between ‘a’ and ‘b’ there is a ‘.’ (dot), so extra state will be added. Between (aa + bb) and (a + b)^* another extra state will also be added.

Step IV: In aa + bb there is a + ,so there will be parallel edges between q₀ and q₂ and in (a + b)^* there is a^*. So between q₂ and q_f there will be L and loop will be on q_f with label (a + b).

Step V: aa and bb there is .(dot). So, two extra states will be added between q₀ and q₂ [one for aa and another bb]. (a + b) on q_f will be made loop with label a,b. Between q₂ and q_f there is a L, that is with no input, control can go to q₂ to q_f. So, q₂ and q_f are equivalent state. The final finite automata for the given Regular Expression will be.

4.4 NFA WITH MOVE AND CONVERSION TO DFA BY - CLOSURE METHOD

Q. What do you mean by NFA with moves? Give an example. Why is it called NFA?

Ans.

If any Finite Automata contains any (null) move or transaction then that Finite Automata is called NFA with moves. As an example

The previous Finite Automata contain two null moves. So the previous FA is NFA with null move.

From the definition of NFA we know for a NFA from a single state for a single input the machine can go to more than one state, i.e. Q X Σ → 2^Q, Where 2^Q is the power set of Q.

From a state by getting input the machine is confined into that state. A Finite Automata with null move must contain at least one move. For this type of Finite Automata for input the machine can go to more than one state. (One is that same state and another state is the - transaction next state). So a Finite Automata with move can be called as a NFA.

For the previous Finite Automata

A NFA with move can be defined as

Where Σ: Set of input alphabets including . and

δ is a transitional function mapping Q X Σ → 2^Q 2^Q is the power set of Q.

Q. Define closure. Clarify it by a suitable example.

Ans. - closure of a state is defined as the set of all states S, such that it can reach from that state to all the states in S with input (i.e. with no input).

Example: Consider the following NFA with moves.

From state q₀ by input (i.e. with no input) we can reach to state q₁ and q₂. With no input we can reach to the same state, i.e. q₀. Therefore, we can write

-closure (q_o) = {q₀ q₁ q₂}

Same like -closure(q₁) = {q₀, q₁, q₂}

-closure (q₂) = {q₀, q₁, q₂} (From q₁ with no input we can reach to q₀, from q₂ with no input we can reach to q₁, so from q₂ with no input we can reach to q₀)

Q. How to convert a NFA with move to a DFA?

Ans. Step I: Find -closure of all the states.

Step II: Construct transitional function δ' for the beginning state for all inputs. The function δ'; will be calculated like the following

Let -closure(A) = {q₁, q₂, q₃} = Q, Therefore the previous equation will become

Step III: First find -closure of the initial state. Rename the set of states as a new state. Then find function δ' of that state for all inputs. If δ' of that state for all inputs is constructed then it is called that the state is marked (Fully Traversed for all the inputs). If any new combinations of state, other than the marked state appear in the process of marking then rename that as a new state.

Step IV: Repeat step III for all new unmarked states. If no the new state appears, then stop construction.

Step V: In this process the states which contain final state as entry are final state of the constructed new DFA.

Q. Convert the following NFA with -move to an equivalent DFA.

Ans.

-closure(q₀) = {q₀, q_l, q₂}. Let rename this state as A. Then construct δ' function for the new unmarked state A for input 0, 1 and 2.

As it is new combination of state other than A so rename it as B.

As it is new combination of state other than A and B so rename it as C.

As δ' is constructed for all inputs on A so A is marked.

B is till unmarked.

Then construct δ' function for the new unmarked state B for input 0, 1 and 2.

As δ' is constructed for all inputs on B so B is marked.

C is till unmarked.

Then construct δ' function for the new unmarked state C for input 0, 1 and 2.

As A, B and C all contain q₂, which is final state, so A, B, C all are final states.

The equivalent DFA

Q. Convert the following NFA with - move to an equivalent DFA.

Ans.

-closure(q₀) = {q₀, q₁, q₃}. Lets rename this state as A. Then construct δ' function for the new unmarked state A for input ‘ a and ‘ b'.

Then construct δ function for the new unmarked state A for input ‘a’ and ‘b’.

As it is new combination of state other than A so rename it as B.

As it is new combination of state other than A and B so rename it as C.

As δ' is constructed for all inputs on A so A is marked.

B is till unmarked.

Then construct δ' function for the new unmarked state B for input ‘a’ and ‘b’.

As it is a new combination of state other than A, B and C so rename it as D.

As δ' is constructed for all inputs on B so B is marked.

C is till unmarked.

Then construct δ' function for the new unmarked state C for input ‘a’ and ‘b’.

As δ' is constructed for all inputs on C so C is marked.

The D is still unmarked.

Then construct δ' function for the new unmarked state D for input ‘a’ and ‘b'.

As the state C contains q₃ so it is final state.

The equivalent DFA is

4.5 EQUIVALENCE OF TWO FINITE AUTOMATA AND TWO REGULAR EXPRESSIONS

Q. What are the steps to declare two Finite Automata equivalents?

Ans. Let there are two Finite Automata M and M' where number of input symbols are the same.

(i) Make a comparison table with n + 1 columns, where n is the number of input symbols.

(ii) In the first column there will be pair of vertices (q, q') where q M and q' M'. The first pair of vertices will be the initial states of the two machines M and M'. Second column consists of (q_a, q_a'). Where q_a is reachable from the initial state of the machine M for the first input, and q'_a is reachable from the initial state of the machine M' for the first input. The other n–2 columns consist of pair of vertices from M and M' for n–1 inputs, where n = 2, 3,…n–1.

(iii) If any new pair of States appears in any of the n―1 next state columns, which were not taken in the First column; take that pair in the present state column and construct subsequent column elements like the first row.

(iv) If a pair of states (q, q') appear in any of the n columns for a pair of states in the present state column, where q is the final state of M and q is the non-final state of M' or vice versa, terminate the construction and conclude that M and M' are not equivalent.

(v) If no new pair of states appears, which were not taken in the First Column and step (iv) does not hold stop construction and declare M and M' are equivalent.

Q. Find whether the two DFAs are equivalent or not.

Ans.

In the previous two DFAs number of input is two, c and d. Therefore in the comparison table there will be three columns. The beginning state pair is (q₀, q₃). From there for input c we are getting (q₀, q₃) and for input d we are getting (q₁, q₄). Among them (q₁, q₄) is the new combination of states which has not appeared yet in the present state column. Hence take it in the present state column and construct next state pairs for input c and d.

After the fourth step no new state combinations have appeared. Hence further construction is stopped. In the whole table no such type of combination of states appears where one state is Final state of one machine and other is the non-final state of another machine.

Therefore, two DFAs are equivalent.

Q. Find whether the two DFAs are equivalent or not.

In the previous two DFAs number of input is two c and d. Hence in the comparison table there will be three columns. The beginning state pair is (q₀, q₃).

(q₀, q₅) is a combination of states where q₀ is the Final state of the machine M and q₅ is the Non-Final state of the machine M'. Hence we shall stop construction declaring two machines are not equivalent.

Q. How will you prove that two Regular Expressions are equivalent?

Ans. For every Regular Expression there is an accepting Finite Automata. If the finite automata constructed from both of the Regular Expressions are same, then we can say that two Regular Expressions are equivalent.

Q. Prove that the following Regular Expressions are Equivalent.

          L1 = (a + b)^* L2 = a^*(b^*a)^*

 

Ans.The Finite Automata for L1 is

Finite Automata for L2 is

We are seeing the Finite Automata Generated by two Regular Expressions, L1 and L2 are same. Hence we can decide that the two Finite Automata are Equivalent.

4.6 CONSTRUCTION OF REGULAR GRAMMAR FROM A REGULAR EXPRESSION

Q. What is the process of generating a Regular Grammar from a Regular Expression?

Ans. From a Regular Expression the Regular grammar for the Regular Expression can be made.

Step I: Construct the equivalent FA for the given Regular Expression (Eliminate all null moves).

Step II: Number of Non-terminals of the grammar will be equal to the number of states of the FA.

Step III: For all transitional functions in the form the production rules will be in the form A→aA₁. If Q₂ is a final state then for the transitional function δ(Q₁,a>→Q₂ the production rules will be A→aA₁ and A→a. The start symbol will be the symbol representing the initial state of the FA.

Q. Construct Regular Grammar for the Regular Expressions.

(i) a^*(a + b)b^*

(ii) ab(a + b)^*

(iii) 10 + (0 + 11)0^*1

Ans.

(i) The Deterministic Finite Automata for the string a^*(a + b)b^* is?

Number of states of the Finite Automata is 2. Hence there will be two non-terminals in the Grammar for the Regular Expression. Lets consider them as A [For q₀] and B [For q₁].

For the transitional function δ(q₀,a)→q₀ the production rule will be A → aA. For the transitional function δ(q₀, a) → q_l the production rule will be A → aB. As q_l is a final state so there will be another production rule A → a

δ(q₀, b) → q₁ : A → bB and A → b (As q₁ is a final state),

δ(q₁, a) → q₁ : B → aB and B → a (As q₁ is a final state),

δ(q₁, b) → q₁ : B → bB and B → b (As q₁ is a final state).

Start symbol will be A as q₀ is the beginning state.

The grammar G for the Regular Expression a^*(a + b)b^* { V_N, Σ, P, S} where

V_N = {A,B},

Σ = {a,b},

P: {A → aA/ bB/a/b, B → aB/bB/a/b},

S: {A},

(ii) The DFA for the string ab(a + b)^* is

There are three states in the DFA. Number of Non-terminals for the Grammar of the Regular Expression will be 3. Let take them as A (For q₀), B(For q₁) and C (For q₂).

For the transitional function δ(q₀, a) → q_l the production rule will be A → aB

δ(q₁, b) → q₂:B → bC and B → b[As q₂ is final state],

δ(q₂, a) → q₂ : C → aC and C → a [As q2₁ is final state],

δ(q₂, b) → q₂ : C → bC and C → b [As q2₁ is final state].

Start symbol will be A as q₀ is the beginning state.

The grammar G for the Regular Expression ab(a + b)^* is {V_N, Σ, P, s}, where

V_N = {A, B, C},

Σ = {a, b},

P: {A → aB, B → bC/b, C → aC/ bC/ a/ b},

S: {A}.

(iii) The NFA without null move for the Regular Expression 10 + (0 + 11)0^*1 is

The equivalent DFA for the above NFA will is

There are four states of the DFA for the Regular Expression 10 + (0 + 11)0^*1. Hence for the Grammar of the Regular Expression there will be four non-terminals. Lets consider them as A [For Q₀], B [For Q₁], C [For Q₂] and D [For Q₃].

Now we have to construct the Production rules of the Grammar.

For the transitional function S(Q₀, 0) → Q_ì , the production rule will be A → 0B

Same like.

δ(Q₀, 1) → Q₂, the production rule will be A → 1C,

δ(Q_V 0) → Q₃ the production rule will be B → 0D and B → 0 (As Q₃ is final state), S(Q₁, 1) → Q₂, the production rule will be B → 1C, S(Q₂, 0) → Q₂, the production rule will be C → 0C,

δ(Q₂, 1) → Q₃, the production rule will be C → 1D and C → 1 (As Q₃ is final state). Start symbol will be A as Q₀ is the beginning state.

The grammar G for the Regular Expression 10 + (0 + 11)0^*1 is {V_N, Σ, P, S}, where

V_N = {A,B,C,D},

Σ ={0,1},

P: {A → 0B/ 1C, B → 0D/ 1C/ 0 , C → 0C/ 1D/ 1},

S: {A}.

(N.B. From NFA without move the Regular Grammar can not be constructed. We can do this by constructing the equivalent DFA)

Q. Define Left-Linear and Right-Linear Grammar. What is the relation between these two forms of grammar? Describe with an example.

Left-Linear Grammar: In a grammar if all productions are in the form A → Bα or A → α then that grammar is called left-linear grammar. Here A and B are non-terminals and α is a string of terminals.

Right-Linear Grammar: In a grammar if all productions are in the form A → αB or A → α then that grammar is called right-linear grammar. Here A and B are non-terminals and α is a string of terminals.

Left-Linear grammar is the reverse of Right-Linear grammar and vice versa. Let there is a regular grammar A → aA/ bB/ b, B → aB/ bB/ a/ b. The grammar is Right-Linear Grammar. The Left-Linear form of the grammar is the reverse of Right-Linear Form.

A → Aa/ Bb/ b, B → Ba/ Bb/ a/b.

4.7 PUMPING LEMMA AND ITS APPLICATION

Q. What is Pumping Lemma for Regular Expression? What is the application of it?

Ans. There is a necessary condition for an input string to belong to a Regular set. This necessary condition is the Pumping Lemma. Pumping means generating. This lemma is called Pumping Lemma because it gives a method of generating many input strings from a given string.

As Pumping lemma is a necessary condition for a string belongs to a Regular set, it is used to prove that certain sets are not regular. If any set fulfills all the conditions of Pumping Lemma it cannot be said confirm that the set is regular.

But the reverse is true, i.e. if any set breaks the conditions of Pumping Lemma it can be said confirm that the set is not regular. So Pumping Lemma is used to prove that certain sets are not regular.

Q. State and prove Pumping Lemma for Regular Expression.

Ans. Pumping Lemma: Let M = {Q, Σ, δ, q₀, F} is a Finite Automata with n number of states. Let L is a Regular Set accepted by M. Let w is a string belongs to the set L and w|≥ m. If m≥ n, i.e. length of the string is greater than or equal to the number of states, then there exists x, y, z such that w = xyz, where|xy| ≤ n,|y| > 0 and xyⁱz L for each i ≥ 0.

[It needs some clarification, after we shall go to the proof section of it.

Lets consider the following Finite Automata. Here from q₀ by getting a it goes to q₁ and from q₁ by getting b it goes to q₂, which is the Final state. The Finite Automata consists of three states, q₀, q₁, q₂. The string that is accepted by the Finite Automata is ba. Length of the string is 2 which is less than the number of states of the Finite Automata.

Here from a state by getting a single input it goes to a single distinct state. But if the length of the string is equal or greater than the number of states of the Finite Automata, then from a state by getting single input it is not possible to get all single distinct states. There must be repetition of at least a single state. This can be described by the following diagrams.

The Regular Expression accepted by the Automata is ba^*b. The expression can be divided into three parts x, y, z where y is the looping portion, x is the portion before looping and z is the portion after the looping portion.]

Proof:

Let w be a string of length m, where m is greater that n, the number of state of the finite automata accepting the string w.

Starting from the beginning state q₀, by getting the string w as input the machine will go to the final state.

In general

The set of the states followed by the string w in the transitional path from beginning state to final state are Q_n = {q₀, q₁, q₂…q_m}. Number of states in the set is m.

But number of states of the Finite Automata accepting the string w is n. As m ≥n so at least two states in the set Q_n must coincide.

Take two integers j and k, where 0 ≤ j< k ≤ n. Among the various pairs of repeated states, take a pair q_j, q_k. The string w can be decomposed into three substrings a₁a_2…… a_j, a_j+1……1 a_k and a_ka_k+1…… a_m Lets denote them as x, y, and z, respectively. As k≤ n so length of the string a_1…a_k is ≤ n, i.e. |xy| ≤ n and w = xyz.

The automaton starts from the initial state q₀. On applying the string x it reaches to the state q_j. On applying the string y it comes back to q_j as q_j = q_k. So on applying the string y, i number of times (where i≤ >0) on q_j, it will be in the same state q_j. On applying z on q_j the automaton will reach to the final state. Hence the string xyⁱzwith i≥ 0 belongs to the language set L, i.e. xyⁱz L.

Q. How Pumping Lemma can be applied to prove that certain sets are not regular?

Ans. Pumping lemma is used to prove that certain sets are not regular. This needs certain steps.

Step I: Assume the set L is regular. Let n be the number of states of the finite automata accepting L.

Step II: Choose a string w (wЄ L) such that | w| ≥ n. By using pumping lemma we can write w = xyz, with |xy| ≤ n and |y| > 0.

Step III: Find a suitable integer i such that xyⁱz ∉ L. This will contradict our assumption. From here L will be declared as not regular.

Q. Show that L = {aⁱ² |i ≥ 1} is not regular.

Ans.

Step I: Assume the set L is regular. Let n be the number of states of the finite automata accepting the set L.

Step II: Let w = aⁿ². |w| = nw² which is greater than n, the number of states of the finite automata accepting L. By using pumping lemma, we can write w = xyz with |xy| < n and |y| > 0.

Step III: Take i = 2. Hence the string will become xy²z.

From step II we know |w| = |xyz| = |x| + |y| + |z| = n².

So |xy²Z| > n²

Again |xy²z|= |x| + 2|y + |z| = |x| + |y| + |z| + |y| = n² + |y|

As |xyj| ≤ n so, |y| ≤ n

Therefore xy²z| ≤ n² + n

From the previous derivations we can write

Hence |xy²z| lies between n² and (n + 1)². They are square of two consecutive positive integers. In between square of two consecutive positive integers no square of positive integer belongs. But aⁱ² where i ≥ 1 is a perfect square of an integer. Hence the string derived from it, i.e. |xy²z| is also a square of an integer, which lies between square of two consecutive positive integers. This is not possible.

So xy²z ∉ L. This is a contradiction.

So, L={aⁱ² |i ≥ 1} is not regular.

Q. Show that L = {a^p|p is prime} is not regular.

Ans.

Step I: Assume the set L is regular. Let n be the number of states in the finite automaton accepting L.

Step II: Let p is a prime number which is greater than n. Let the string w = a^p, w ∉ L. By using Pumping lemma we can write w = xyz with |xy| ≤ n and |y| > 0. As the string w consists of only 'a so x, y, and z are also string of ‘a’s. Let y = a^m for some m with 1 ≤ m ≤ n.

Step III: Let take i = p + 1. |xy¹z| will be |xyz| + |y^i-1|

p(1 + m) is not a prime number as it has factors p and (1 + m) including 1 and p(1 + m). Hence, xyⁱz ∉ L. This is a contradiction.

Therefore L = {a^p | p is prime} is not regular.

Q. Show that L={aⁿ³ | i ≥ 1} is not regular.

Ans.

Step I: Assume the set L is regular. Let n be the number of states of the finite automata accepting the set L.

Step II: Let L = aⁿ³. The |w| = n³ which is greater than n, the number of states of the finite automata accepting L. By using pumping lemma, we can write w = xyz with |xy| ≤ n and |y| > 0.

Step III: Consider i = 3. Therefore the string will become xy³z.

We can write

n³ < |xy³z| < (n + 1)³

xy³z is a perfect cube which lies between n³ and (n + 1)³, i.e. two consecutive perfect cube numbers. In between cube of two consecutive positive integers no cube of positive integer belongs. But aⁱ³ where i≥ 1 is a perfect cube of an integer. Hence the string derived from it, i.e. xy³z is also a cube of an integer, which lies between cube of two consecutive positive integers. This is not possible. Therefore xy³z ∉ L. This is a contradiction. So, L={aⁱ³ |i ≥ 1} is not regular.

Q. Show that L={aⁿbⁿ where n ≥ 1} is not regular.

Ans.

Step I: Suppose the set L is regular. Let n be the number of states of the finite automata accepting L.

Step II: Let w = aⁿbⁿ, |w| = 2n > n. By pumping lemma we can write w = xyz with |xy| ≤ n and |y> 0.

Step III: We want to find a suitable i so that xyⁱz ∉ L . The string y can be of any of the following:

(i) y is a string of only ‘a’, i.e. y = a^k for some k ≥ 1

(ii) y is a string of only ‘b’, i.e. y = b^k for some k ≥ 1

(iii) y is a string of both ‘a’, and ‘b’, i.e. y = a^kb¹ for some k, l ≥ 1

For Case (i)

For Case (ii)

For Case (iii)

a^n-ka^k b¹ a^k b¹ b^n-k = aⁿb¹a^kbⁿ, which is not in the form aⁿbⁿ. So xy²z ∉ L

For all the three cases we are getting contradiction. Therefore L is not regular.

Q. Show that L = palindrome over {a,b} is not regular.

Ans.

Step I: Suppose the set L is regular. Let n be the number of states of the finite automata accepting L.

Step II: Let w = aⁿbaⁿ, |w| = (2n + 1) > n. By pumping lemma we can write w = xyz with |xy| ≤ n and |y| > 0.

Step III: We want to find a suitable i so that xyⁱz ∉ L. The string y may consists of only ‘a’ let a^j where j > 0. Let take i = 0. xyz = aⁿbaⁿ = a^n-ja^j baⁿ. Therefore xy⁰z = a^n-Jbaⁿ.

As j > 0, n - j ≠ n. So a^n-jbaⁿ; is not a palindrome.

So xy⁰z ≠ L. Hence it is proved that L is not Regular.

Q. Show that L = { ww, where w ∈ (a,b)^*} is not regular Ans.

Step I: Let consider the set L is regular. Let n be the number of states of the finite automata accepting L.

Step II: Let ww = aⁿbaⁿb ∉ L, so |ww| = 2(n + 1) > n. By applying pumping lemma we can write w = xyz with |xy| ≤ n and |y| > 0.

Step III: We want to find a suitable i so that xyⁱz ∉ L. The string consist of ‘a’ and ‘b’. Therefore y can be of any of these

(i) y has no ‘b’, i.e. y = a^k.

(ii) y has only one ‘ b' (because the string is aⁿbaⁿb).

Let take i = 0 in case I. If i = 0, then xy⁰z = xz and it is in the form a^n-kbaⁿb or aⁿba^n-kb.

This is not in the form ww, i.e. xz ∉ L. Hence L is not regular.

In case II, if we take i = 0 then xy⁰z = xz which contain only one ‘b’. Which is not in the form ww, i.e. xz ∉ L. Hence L is not regular.

Q. Show that L = {aⁿbaⁿ, where n ≥ 1} is not regular.

Ans.

Step I: Assume that L is regular. Let n be the number of states of the finite automata accepting L.

Step II: Let w = aⁿbaⁿ. Hence |w| = 2n + 1 > n. According to pumping lemma we can write w = xyz, with w = xyz with |xy| ≤ n and |y| > 0.

Step III: We want to find a suitable i so that xyⁱz ∉ L. The string consist of ‘a’ and ‘b’. So y can be of any of these:

(i) y has no ‘b’, i.e. y = a^k

(ii) y has only one ‘b’ [because the string is aⁿbaⁿ]

For Case I take i = 2.

The string xyz = a^n-k a^kbaⁿ or aⁿba^ka^n-k

Therefore, xy²z=a^n-ka^2kbaⁿ=a^{n + k}baⁿ or aⁿba^2ka^n-k=aⁿba^{n + k}.

As k ≠ 0, (n + k) ≠ n. Therefore xy²z ∉ L.

This is a contradiction so L is not regular.

For Case II let take i = k. So xy^kz = aⁿb^kaⁿ. This is not in the form aⁿbaⁿ. Therefore xy^kz ∉ L.

This is a contradiction so L is not regular.

Q. Show that L = {aⁿbⁿabⁿ⁺¹} is not regular.

Ans.

Step I: Assume that L is regular. Let n be the number of states of the finite automata accepting L.

Step II: Let w = aⁿbⁿabⁿ⁺¹, so |w| = (3n + 2) > n. By using pumping lemma we can write w = xyz, with w = xyz with |xy| ≤ n and |y| > 0.

Step III: We want to find a suitable i so that xyⁱz ∉ L. The string consist of ‘a’ and ‘ b’. Hence y can be of any of these

(a) y contain only ‘a’, let y = a^k.

(b) y contain only ‘b’, let y = b¹

(c) y contain ‘a’ and ‘b’ both, let y = b^ka.

For case I, take i = 0.

w = xyz = (a^n-k )(a^k )(bⁿabⁿ⁺¹)

xy°z = a^n-k bⁿabⁿ⁺¹ which is not in the form aⁿbⁿabⁿ⁺¹.

For case II take i = 0

w = xyz = (a^n-k)kⁿbⁿabⁿ⁺¹

xy⁰z = aⁿb^n-1 abⁿ⁺¹ which is not in the form aⁿbⁿabⁿ⁺¹.

For case III, take i = 2

w = xyz = aⁿb^n-k(b^ka)² bⁿ⁺¹

= aⁿbⁿa b^kabⁿ⁺¹, which is not in the form aⁿbⁿabⁿ⁺¹.

In all the three cases there are contradiction, hence the language is not regular.

Q. Show that the language containing the set of all balanced parenthesis is not regular.

Ans.

Step I: Assume that L is regular. Let n be the number of states of the finite automata accepting L.

Step II: Let w = (((….()….))) = (ⁿ)ⁿ . |w| = 2n > n. By using pumping lemma we can write w = xyz, with w = xyz with |xy| ≤ n and |y| > 0.

Step III: We want to find a suitable i so that xyⁱz ∉ L. The string consists of ‘(’ and ‘)’. So y can be of any of these

(a) y consists of only ‘(’ let y = (^k

(b) y consists of only ‘)’, let y = )^k

(c) y consists of both ‘(’ and ‘)’, let y = (^k)^k

For case I, take i =0.

w = xyz = (^n-k ( ^k)ⁿ

xy⁰z = (^n-k)ⁿ which is not set of all balanced parenthesis.

For case II, take i = 0.

w = xyz = (ⁿ ) ^k)^n-k

xy⁰z = (ⁿ)^n-k which is not set of all balanced parenthesis.

For case III, take i = 2.

w = xyz = (^n-k(^k)^k)^n-k

xy²z = (ⁿ)^k(^k)ⁿ which is not set of all balanced parenthesis.

In all the three cases there are contradiction, hence the language is not regular.

Regular Expression

Q. Show that L = {0ⁿ1²ⁿ, where n > 1 } is not regular.

Ans

Step I: Assume that L is regular. Let n be the number of states of the finite automata accepting L.

Step II: Let w = 0“1²”, where n³ 1. |w| = 3n > n. By using pumping lemma we can write w = xyz, with |xy| , n and |y| - 0.

Step III: We want to find a suitable i so that xy'z ∉ L. The string consists of ‘0' and ‘1'. y can be any of the following forms

y consists of only ‘0', let y = 0^k

y consists of only ‘1', let y = 1^k

y consists of both ‘0' and ‘1'. Let y = 0^k1^k

For case I, take i = 0.

For case II, take i = 0.

For case III, take i=2.

For all the three cases we are getting contradiction, therefore L is not regular.

4.8 CLOSURE PROPERTIES OF REGULAR SET

Q. What do you mean by closure property? Give an example.

Ans. A set is closed (under an operation) if and only if the operation on two elements of the set produces another element of the set. If an element outside the set is produced, then the operation is not closed. Closure is a property which describes when we combine any two elements of the set; the result is also included in the set.

If we multiply two real numbers, we will get another real number. Since this process is always true, it is said that the real numbers are “closed under the operation of multiplication”. There is simply no way to escape the set of real numbers when multiplying.

Let S = {1,2,3,4,5,6,7,8,9,10,…} is a set of real numbers.

1 × 2 = 2,

2 × 3 = 6,

5 × 2 = 10.

All are included in the set of real numbers.

Therefore we can say real numbers are closed under the operation of multiplication.

Q. Prove that two Regular Expressions L_l and L₂ over Σ are closed under union operation.

Ans. We have to prove that if L₁ and L₂ are regular over Σ, then their union, i.e. L₁ ∪ L₂ will be also regular.

As L₁ and L₂ are regular over Σ, there must exist finite automata M₁ = (Q₁, Σ, δ₁, q₀₁, F₁) and M₂ = (Q2, Σ, δ₂, q₀₂, F₂) such that L₁ ∈ M₁ and L₂ ∈ M₂

Assume that there is no common states between Q₁ and Q₂, i.e. Q₁ ∩ Q₂ = ∧.

Define another Finite Automata M₃ = (Q, Σ, δ, q₀, F), where

(i) Q = Q₁ ∪ Q₂ ∪ {q₀}, where q₀ is a new state g Q₁ ∪ Q₂

(ii) F = F1 ∪ F2

(iii) Transitional function δ is defined as δ(q , e) → {q₀₁, q₀₂} and δ(q, Σ) δ₁(q, Σ) if q ∈ Q₁

     δ(q, Σ) → δ₂{q, Σ)if q ∈ Q₂

It is clear from the previous discussion that from q₀ we can reach to either initial state q₁ of M₁ or initial state q₂ of M₂.

Transitions for the new Finite Automata M are same like the transitions of M₁ and M₂. As F = F₁ ∪ F₂ so any string accepted by M₁ or M₂ will also be accepted by M Therefore L₁ ∪ L₂ is also regular.

Example:

The Finite Automata M₁ accepting L₁ is

The Finite Automata M2 accepting L2 is

The machine M produced by combining M1 and M2 is

It accepts L₁ u L,

Q. Prove that complement of a Regular Expression is also regular.

Ans. If L is regular we have to prove that L_T is also Regular.

As L is Regular there must be a Finite Automata M = (Q, Σ, δ, q₀ , F) accepting L. M is a Finite Automata, so M has a transitional system.

Let construct another transitional system M' with the state diagram of M but reversing the direction of the directed edges. M' can be designed as follows

(i) set of states of M' is same as M

(ii) set of input symbols of M' is same as M

(iii) Initial state of M' is same as Final state of M [M' is reverse direction of M]

(iv) Final state of M' is same as initial state of M [M' is reverse direction of M]

Let a string w belongs to L, i.e. w ∈ M. Therefore, there is a path from q₀ to F with path value w. By reversing the edges we get a path from F to q₀ (Beginning and Final state of M’) in M'. The path value is reverse of w, i.e. w_T. Therefore w_T ∈ M'.

so the reverse of the string w is regular.

Let L = ab(a+b)*

The Finite Automata M accepting L is

The reverse of The fi nite automata accepting L^c is

M' accepts (a+b)*ba which is reverse of L.

Therefore w ∈ L, i.e. Σ* - LL. However, Σ* - L is accepted by M' which is a Finite Automata.

Replace this by Σ* - L ≠ L

Q. If L is regular and L is a subset of Σ*, prove that Σ* - L is also a regular set.

Ans. As L is Regular there must be a Finite Automata M = (Q, Σ, δ, q₀, F) accepting L. Let construct another DFA M' = (Q, Σ, δ, q₀, F’), where F' = Q-F. Therefore two DFA differ only in their final states. A final state of M is a nonfinal state of M' and vice versa.

Let take a string w which is accepted by M'. Therefore Σ^₀, w) e F', i.e. Σ^₀, w) e (Q - F).

The string w cannot be accepted by M, because Σ^₀, w) g F[As F does not belong to (Q - F)].

Therefore w g L, i.e. Σ* - L Σ L. However, Σ* - L is accepted by M' which is a Finite Automata.

Therefore Σ_* - L is a regular set

Q. Prove that two Regular Expressions L₁ and L₂ over Σ are closed under intersection operation.

Ans. From D'Morgan's theorem we know

We know if L_l and L₂ are regular then L_l^C and L₂^C are also regular.

As L_l^C and L₂^C are regular, L_l^C L₂^C is also regular (Regular Expression are closed under union operation.)

As L_l^C L₂^C is regular so their complement (L_l^C L₂^C)_C is also regular.

So L_l L₂ is also regular, i.e. the regular sets are closed under intersection.Σ

WHAT WE HAVE LEARNED SO FAR

1. A Regular Expression can be defined as a language or string accepted by a Finite Automata.

2. Any terminal symbols, null string (Σ), null set (Σ) are Regular Expression.

3. Union, Concatenation, Iteration of two Regular Expressions or any combination of them are also Regular Expression.

4. Arden's Theorem states that if P and Q be two Regular Expressions over Σ. If P does not contain Σ, then for the equation R=Q + RP has a unique (one and only one) solution R=QP*.

5. Arden's Theorem is used to construct Regular Expression from a given Finite Automata by Algebraic Method.

6. If any Finite Automata contains any e (null) move or transaction then that Finite Automata is called NFA with e moves.

7. e - closure of a state is defined as the set of all states s, such that it can reach from that state to all the states in s with input e (i.e. with no input).

8. Pumping Lemma for Regular Expression is used to prove that certain sets are not regular.

9. A set is closed (under an operation) if and only if the operation on two elements of the set produces another element of the set.

10. Closure is a property which describes when we combine any two elements of the set; the result is also included in the set.

11. Regular Expressions are closed under Union, Complementation, and Intersection operation.

SOLVED PROBLEMS

1. Describe the following Regular Expressions in English Language.

(i) a(a + b)*b

(ii) (a + b)*aba(a + b)*

(iii) (0 + 1)*1(0 + 1)*0(0 + 1)*

Ans. (i) The language starts with 'a and ends with 'b'. In the middle of 'a and 'b' there is any combination of 'a and ‘b'. Hence the Regular Expression described in English language

{set of any combination of ‘a' and ‘b' beginning with ‘a' and ending with ‘b'}

(ii) The expression is divided into three parts (a + b)*, aba, and (a + b)*. In each element of the language set there is aba as substring. In English language, the Regular Expression is described as

{set of any combination of ‘a' and ‘b' containing ‘aba' as substring}

(iii) The expression is divided into five parts (0 + 1)*, 1, (0 + 1)*, 0 and (0 + 1)*. In each element of the language set there is 1 and 0, where 1 appears first. In English language the Regular Expression is described as

{set of any combination of ‘0' and ‘1' containing atleast one 1 and one 0}.

 

2. Find Regular Expression for the following:

(a) Set of Languages of any combination of ‘a' and ‘b' beginning with ‘a'.

(b) Set of languages of any combination of ‘0' and ‘1' containing atleast one double symbol.

(c) Set of languages of any combination of ‘0' and ‘1' containing no double symbol

Ans. (a) Set of any combination of 'a and 'b' is denoted by (a + b)*. The Regular Expression is

L = a(a + b)*.

 

(b) The language consists of two symbols ‘0' and ‘l'. Double [same] symbol means either 00 or ll. Part of the language containing atleast one double symbol is denoted by (00 + ll). Therefore the language of any combination of ‘0' and ‘l' containing atleast one double symbol is expressed as L = (0 + 1)* (00 + 11) (0 + 1)*.

(c) The language consists of two symbols ‘0' and ‘l'. Double [same] symbol means either 00 or ll. According to the condition, in the language 00 or ll will not appear. The language may start with ‘0' or start with ‘l'. The language start with ‘0' with no double symbol is (0l)*. The language start with ‘l' with no double symbol is (l0)*.

The expression is L = (01)* + (10)*

 

3. Construct a Regular Expression from the given Finite Automata by Algebraic Method using Arden's Theorem.

Ans. For the above given Finite Automata the equations

Put the value of q₀ in equation q_l. q_l = 0 + q_l0. The equation is in the form R = Q + RP, where R = q_l, Q = 0 and P = 0. By Arden theorem the solution of the equation is R = QP* i.e.

ql = 00*.

Substituting the value q_l in equation (3) we get q₂ = 00*l + q₂l.

The equation is in the form R = Q + RP, where R = q₂, Q = 00*1 and P = 1. By Arden theorem the solution of the equation is R = QP* i.e.

q₂ = 00*11*.

Substituting the value of q_, and q₀ in equation (4) we get

q₃ = (00*11*0 + 1) + q₃ (0 + 1).

The equation is in the form R = Q + RP, where R = q₃, Q = (00*11*0 + 1) and P = (0 + 1). By Arden theorem the solution of the equation is R = QP* i.e.

q₃ = (00*11*0 + 1) (0 + 1)*.

As q₃ is the final state so the Regular Expression generated from the given Finite Automata is (00*11*0 + 1) (0+ 1)*.

 

4. Construct a Regular Expression from the given Finite Automata by Algebraic Method using Arden's Theorem.

Ans. For the above given Finite Automata the equations will be

The equation (1) is in the form R = Q + RP, where R = A, Q = Σ and P = b. According to Arden's Theorem, the solution for the equation is R = QP*.

Therefore, A = Σ^ = b' [As ΣR = R Σ = R].

Substituting the value of A in equation (2) we get

B = b'a + Bb

The equation is in the format R = Q + RP, where R = B, Q = b'a, and P = b. According to Arden's Theorem, the solution for the equation is R = QP*.

Therefore, B = b* ab*.

Substituting the value of B in equation (3) we get

C = b'ab'a + C(a + b).

The equation is in the format R = Q + RP, where R = C, Q = b'ab'a and P = (a + b). According to Arden's Theorem, the solution for the equation is R = QP*.

So C = b_*ab_*a(a + b)_*.

As C is the final state so the Regular Expression accepted by the finite automata is b_*ab_*a(a + b)_*

5. Construct a Regular Expression from the given Finite Automata by Algebraic Method using Arden's Theorem.

Ans. For the above given Finite Automata the equations will be

The equation (1) is in the form R = Q + RP, where R = A, Q = Σ, and P = a. According to Arden's Theorem, the solution for the equation is R = QP^*.

Therefore

substituting the value of A in equation (2) we get

substituting the value of B in equation (3) we get

This is in the format R = Q + RP, where R = C, Q = a^*bb, and P = b. According to Arden's Theorem, the solution for the equation is R = QP^*.

C = a^*bbb^*.

substituting the value of B and C in equation (4) we get

D = a^*ba + a^*bbb^*a + D(a + b).

This is in the format R = Q + RP, where R = D, Q = a^*ba + a^*bbb^*a and P = a + b. According to Arden's Theorem, the solution for the equation is R = QP^*.

In the finite automata there are two final states B and D. Therefore, the Regular Expression accepted by the finite automata:

6. Construct Finite Automata equivalent to the Regular Expression.

L = (a + b) + (ab + ba)(a + b)^*

Ans. Step I: Take a beginning state q0 and a final state q_f. Between the beginning and fi nal state place the Regular Expression.

Step II: Between (a + b) and (ab + ba)(a + b)^* there is a ‘ + ’ sign, so there will be parallel edges between q₀ and q_f.

Step III: Between (ab + ba) and (a + b)^* there is a ‘.' (dot) sign, so a extra state is added between q₀ and q_f.

Step IV: Between ab and ba there is ‘ + ’ sign, so there will be parallel edges between q₀ and q_l.

Step V: Between ‘a’ and b there is ‘ + ’ sign. Therefore, between q₀ and q_f there is parallel edge. As there is a ‘^*’ in (a + b), hence a loop is added on q_f and an ∈ is added between q_l and q_f.

Step VI: Between ‘a’ and ‘b’ and between ‘b’ and ‘a’ there are ‘.’(dot). Therefore, two extra states are added between q₀ and q₁.

Step VII: Between q_l and q_f there is an . To remove that , merge q_l and q_f. Now two transition from q₂ and q₃ is added on q_f.

7. Construct Finite Automata equivalent to the Regular Expression.

L = (00 + 11)^* 11 (0 + 1)^*

Ans.

Step I: Take a beginning state q₀ and a final state q_f. Between the beginning and final state place the Regular Expression.

Step II: There are three ‘.’ (dot) in between (00 + 11)^* and 1, 1 and 1, and 1 and (0 + 1)^*. So three extra states are added in between q₀ and q_f.

Step III: There are two ^* in the Regular Expression. Hence, there will be self loop on q₁ and q_f. And transition will be in between q₀ and q₁, and q₃ and q_f.

Step IV: There is a ‘ + ‘ sign between 00 and 11, hence there will be parallel edges. And two ‘.'(dot) sign (between 0, 0 and 1,1) Hence two extra states are added.

Step V: Removing , the final automata becomes

8. Convert the following NFA with ∈ -move to an equivalent DFA.

Ans.

-closure (0) = {0,1,2,4,7}

-closure (1) = {1, 2, 4, 5}.

-closure (2) = {2}

-closure (9) = {9}

-closure (3) = {1, 2, 3, 4, 6, 7}

-closure (4) = {4}

-closure (5) = {1, 2, 4, 5, 6, 7}

-closure (10) = {10}

-closure (6) = {1, 2, 4, 6, 7}

-closure (7) = {7}

-closure (8) = {8}

As 0 is the beginning state so start with -closure(0) = {0,1,2,4,7}. Let rename it as A.

A is till unmarked.

Then construct δ' function for the new unmarked state A for input a and b.

New state so rename it as B.

New state so rename it as C.

B is till unmarked.

Then construct δ' function for the new unmarked state B for input a and b.

New state so rename it as D.

C is till unmarked.

Then construct δ' function for the new unmarked state C for input a and b.

D is till unmarked.

Then construct δ' function for the new unmarked state D for input a and b.

New state so rename it as E.

Here final state is E.

The equivalent DFA:

9. Construct Regular Grammar for the Regular Expression L = (a + b)^*(aa + bb)(a + b)^*

Ans. The NFA for the Regular Expression

There are four states in the finite automata. Therefore, in the regular grammar there are four nonterminals.

Lets consider them as A [For q₀], B [For q1, C [For q₂] and D [For q₃].

Now we have to construct the Production rules of the Grammar.

For the state q₀ the production rules are

A → aA, A → bA, A → aB, A → bC.

For the state q₁ the production rules are

B → aD, B → a [As D is final state].

For the state q₃ the production rules are

C → bD, C → b [As D is final state].

For the state q₄ the production rules are

D → aD, D → bD, D → a/b

The grammar = {V_N, S, P, S}

V_N = {A, B, C, D} S ={a, b}

MULTIPLE CHOICE QUESTIONS

1. Machine format of Regular Expression is

(a) Finite Automata

(b) Push Down Automata

(c) Turing Machine

(d) All of the above.Σ

2. Regular Expression is accepted by

(a) Finite Automata

(b) Push Down Automata

(c) Turing Machine

(d) All of the above.

3. The language of all words with atleast 2 a's can be described by the Regular Expression (a) (ab)^*a

(b) (a + b)^*ab^*a(a + b)^*

(c) b^*ab^*a(a + b)^*

(d) All of the above

4. Which type of language is Regular Expression?

(a) Type 0

(b) Type 1

(c) Type 2

(d) Type 3.

5. Which of the following Regular Expression over {0,1} denotes set of all strings not containing 100 as substring?

(a) (1 + 0)^*0^*

(b) 0^*1010^*

(c) 0^*1^*01

(d) All of the above.

6. Σ + RR^* = ?

(a) R

(b) R^*

(c) R +

(d) Σ.

7. What is the solution for the equation R = Q + RP (If P and Q are Regular Expression and P does not contain ∧)

(a) R = QP^*

(b) R = QP

(c) R = PQ^* (d) R = P^*Q^*.

8. Which is true for e -closure of a state.

(a) All the states reachable from the state with input null excluding the state

(b) The state only

(c) All the other states

(d) All the states reachable from the state with input null.

9. Pumping lemma for Regular Expression is used to prove that

(a) Certain sets are Regular

(b) Certain Sets are not Regular

(c) Certain Regular Grammar produce Regular Expression

(d) Certain Regular Grammar does not produce Regular Expression

10. Regular sets are closed under

(a) Union

(b) Concatenation

(c) Kleene Closure

(d) All of the above.

Ans. 1. a 2. d 3. b 4. d 5. c 6. b 7. a 8. d 9. b 10. d.

EXERCISES

1. Prove that (0 + 011^*) + (0 + 011^*)(01 + 0100^*)(01 + 0100^*)^* = 01^*(010^*)^*.

2. Find Regular Expression for the followings

(a) Set of all strings over (a, b) containing exactly one a

(b) Set of all strings over (a, b) containing atleast two a's

(c) Set of all strings over (0, 1) containing exactly two a's

(d) Set of all strings over (a, b) beginning and ending with b.Σ

(e) Set of all strings over (0, 1) containing 010 as substring

(f) Set of all strings over (0, 1) not containing substring 00.

3. Describe the following Regular Expressions in English language

(a) b'ab'

(b) (a + b)^* aba(a + b)'

(c) a(a + b)^*ab

4. Find Regular Expressions corresponding to the automaton generated by the following Finite Automata.

5. Convert the following NFA with null move to an equivalent DFA by closure method.

6. Develop Finite Automata for the following Regular Expressions

(a) (a^*ab + ba)^*a^*

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

(c) 10 + (0 + 11)0^*1

7. Construct Regular Grammar for the following Finite Automata.

(a) ab + (aa + bb)(a + b)^*

(b) 01(00 + 11)^*11^*

(c) a^*(aa + bb)^* + b^*(ab + ba)^*

8. Using Pumping Lemma show that following sets are not regular.

(a) L = {aⁿb^m, where 0 < n < m}

(b) L = {aⁿbⁿ + ¹, where n > 0}

(c) L = {aⁱb^jc^k, where i,j,k > 0}

FILL IN THE BLANKS

1. Regular Expression is a string on_______among {Q, Σ, δ, q₀, F}

2. If R is a Regular Expression then Λ + RR* =_______.

3. According to Arden's Theorem the solution of the equation R=Q+RP is_______.

4. Set of all states that can be reached from that state to all the states with input is called_______

5. For the following NFA with move closure of ql is_______

6. A grammar where all productions are in the form A → Ba or A → a then that grammar is called_______

7. A grammar where all productions are in the form A → aB or A → a then that grammar is called_______

8. Pumping Lemma for Regular Expression is used to prove that certain sets are not_______

9. The property which describes when we combine any two elements of the set; the result is also included in the set is called_______

10. If any Finite Automata contains any (null) move or transaction then that Finite Automata is called_______.

11. Machine format of Regular Expression is_______

ANSWERS

1. Σ

2. R*

3. R = QP^*

4. closure

5. q0, q1, q2

6. left linear grammar

7. right linear grammar

8. Regular

9. Closure property

10. NFA with moves

11. Finite Automata