# Regular language & Expression

Regular language & Expression is the important topic of the Theory Of Computation. Theory Of Computation is the Important subject of the Computer.

**Regular Language**

A Regular Language over an alphabet ∑ is one that can be obtained from this basic language using the operation of Union, Concatenation and Kleene (*).

**Regular Expression**

Regular Language can be described by an explicit formula.

It is common to simplify the formula slightly by leaving out the set brackets {} or replacing them with parenthesis () and replace U by +. The result is called Regular Expression. **Table – Regular Expression**

**More Examples of Regular language & Expression**

1) 0 or 1

0+1

2) 0 or 11 or 111

0+11+111

3) Regular expression over ∑={a,b,c} that represent all string of length 3. (a+b+c)(a+b+c)(a+b+c)

4) A string having zero or more a.

a*

##### 5) The string having one or more a.

a^{+}

6) All binary string.

(0+1)*

7) 0 or more occurrence of either a or b or both

(a+b)*

8) 1 or more occurrence of either a or b or both

(a+b)^{+}

9) Binary no. ends with 0

(0+1)*0

##### 10) Binary no. ends with 1

(0+1)*1

11) Binary no. starts and ends with 1.

1(0+1)*1

12) The string starts and ends with the same character.

0(0+1)*0 or a(a+b)*a

1(0+1)*1 b(a+b)*b

13) All string of a and b starting with a

a(a/b)*

14) The string of 0 and 1 ends with 00.

(0+1)*00

15) The string ends with abb.

(a+b)*abb

##### 16) The string starts with 1 and ends with 0.

1(0+1)*0

17) All binary string with at least 3 characters and 3rd character should be zero.

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

18) Language which consist of exactly two b’s over the set ∑={a,b}

a*ba*ba*

19) ∑={a,b} such that 3rd character from right end of the string is always a.

(a+b)*a(a+b)(a+b)

20) Any no. of a followed by any no. of b followed by any no. of c.

a*b*c*

##### 21) The string should contain at least 3 one.

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

22) String should contain exactly two 1’s

0*10*10*

23) Length of a string should be at least 1 and at most 3.

(0+1) + (0+1) (0+1) + (0+1) (0+1) (0+1)

24) zero should be multiple of 3

(1*01*01*01*)*

25) ∑={a,b,c} where a should be multiple of 3. ((b+c)*a (b+c)*a (b+c)*a (b+c)*)* 26. Even no. of 0.

(1*01*01*)*

26) Odd no. of 1.

0*(10*10*)*10*

##### 27) The string should have odd length.

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

28) String should have even length.

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

29) String start with 0 and has odd length.

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

30) String start with 1 and has even length.

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

##### 31) Even no of 1

(0*10*10*)*

32) Moreover, String of length 6 or less

(0+1+^)^{6}

33) String ending with 1 and not contain 00.

(1+01)^{+}

34) All string begins or ends with 00 or 11.

(00+11)(0+1)*+(0+1)*(00+11)

35) Moreover, Language of all string containing both 11 and 00 as substring. (( 0+1)*00(0+ 1)*11(0 +1)*)+ ((0+ 1)*11 (0+1)*00(0+1)*)

36) Language of C identifier.

(_+L)(_+L+D)*

**Related Terms**

Theory of Computation, PDA – CFG, Mathematical Induction, Context Free Grammar

## Leave a Reply