Regular Languages

Ardens Theorm

Arden's Theorem:

One of the applications of Arden's Lemma is, in the conversion of FA to RE.

Statement:

if P and Q are two regular expressions over Σ and P does not contain ε then

R= Q+ RP has a unique solution and it is given by

R=QP^*

Prove:

R = Q + RP

= Q + (Q+ RP)P // repacing R with Q + RP

= Q + QP + RP²

= Q + QP + (Q+ RP)P²

= Q + QP + QP² + RP³

= Q + QP + QP² + QP³ + QPⁿ +QPⁿPⁿ⁺¹

=Q(ε + P+P² + P³ + Pⁿ +PⁿPⁿ⁺¹ )

= QPⁿ

= QP^*

0Comment

thumbs up down

Operations on Regular Languages | Union | Intersection | Concatenation | Kleene Closure | Complement | Power of a String:

1. Union : If L1 and If L2 are two regular languages, their union L1 ∪ L2 will also be regular.

For example, L1 = {aⁿ | n ≥ 0} and L2 = {bⁿ | n ≥ 0}
L3 = L1 ∪ L2 = {aⁿ ∪ bⁿ | n ≥ 0} is also regular.

2. Intersection : If L1 and If L2 are two regular languages, their intersection L1 ∩ L2 will also be regular.

For example,
L1= {a^m bⁿ | n ≥ 0 and m ≥ 0} and L2= {a^m bⁿ ∪ bⁿ a^m | n ≥ 0 and m ≥ 0}
L3 = L1 ∩ L2 = {a^m bⁿ | n ≥ 0 and m ≥ 0} is also regular.

3. Concatenation : If L1 and If L2 are two regular languages, their concatenation L1.L2 will also be regular.

For example,
L1 = {aⁿ | n ≥ 0} and L2 = {bⁿ | n ≥ 0}
L3 = L1.L2 = {a^m . bⁿ | m ≥ 0 and n ≥ 0} is also regular.

4. Kleene Closure : If L1 is a regular language, its Kleene closure L1* will also be regular.

For example,
L1 = (a ∪ b)
L1* = (a ∪ b)*

5. Complement : If L(G) is regular language, its complement L’(G) will also be regular. Complement of a language can be found by subtracting strings which are in L(G) from all possible strings.

For example,
L(G) = {aⁿ | n > 3}
L’(G) = {aⁿ | n <= 3}

Note :

Two regular expressions are equivalent if languages generated by them are same. For example, (a+b*)* and (a+b)* generate same language. Every string which is generated by (a+b*)* is also generated by (a+b)* and vice versa.

Power of a String:

Consider ∑ = {0, 1}. The following are the power of an alphabet over input alphabet ∑.

(L)∑ = {null}: zero length string

(L)∑ = {0, 1}: set of 1 length string

(L)∑ = {01, 10, 11}: set of 2 length string

0Comment

thumbs up down

Theory of Computation : Basic Terms | Power of an alphabet: | Algebraic Structure | Set of a String

Theory of Computation is a branch of computer science that deals with designing abstract self-propelled computing devices that follow a predetermined sequence of operations automatically.

Theory of Computation – Basic Terms:

Symbols:

Theory of computation is entirely based on symbols. These symbols are generally letters and digits.

Example: 0, 1 are symbols of binary digits

A, B, C, …., Z is symbols of letter alphabet.

Alphabet:

An alphabet is any finite set of symbols.

Example − ∑ = {a, b, c, d} is an alphabet set where ‘a’, ‘b’, ‘c’, and‘d’ are symbols.

∑ = {0, 1} is an alphabet of binary digits set where ‘0’, ‘1’ are symbols.

To represent alphabet in automata we use Σ (sigma symbol).
Now there is a rule for checking the validation of alphabets on the basis of which we declare a set of symbols or a symbol valid or invalid.

Rule:

If we have used any alphabet then it should not be prefix in the next combination or alphabet.

Σ = {a, b} ✓ Valid

Σ = {a, ba, c} ✓ Valid

Σ = {a, ab, c} ☓ Invalid

Σ = {0, 10} ✓ Valid

Σ = {1, 10, 11} ☓ Invalid

Power of an alphabet:

Consider ∑ = {a, b}. The following are the power of an alphabet over input alphabet ∑.

∑ = {null}: zero length string

∑ = {a, b}: set of 1 length string

∑ = {aa, ab}: set of 2 length string

Algebraic Structure

A non empty set S is called an algebraic structure with respect to binary operation if (a*b) belongs to S for all (a*b) belongs to S, i.e (*) is closure operation on ‘S’.

Ex : S = {1,-1} is algebraic structure under *

As 1*1 = 1, 1*-1 = -1, -1*-1 = 1 all results belongs to S.

But above is not algebraic structure under + as 1+ (-1) = 0 not belongs to S.

String

String is a finite sequence of symbols taken from ∑.

Ex : ‘ cabcad ’ is a valid string on the alphabet set ∑ = {a, b, c, d}

Set of a String :

Definition – The set of strings, including the empty string, over an alphabet ∑ is denoted by ∑*.
Examples − For ∑ = {0, 1} we have set of strings as ∑* = {є, 0, 1, 01, 10, 00, 11, 10101,…}.
and ∑1 = {0, 1} , ∑2 = {00, 01, 10, 11} and so on.

∑* contains an empty string є. The set of non- empty string is denoted by ∑+.

0Comment

thumbs up down