Question & Answer: Let L be a regular language. Define End(L, a) {x: x elementof L and x is ended with symbol a}……

Question #2

Regular expression is a notation in compiler design that specifies pattern defined by the language rules. Each pattern matches a set of strings and validates the structure of program sentence. If fails, compiler throws an error.

Operations:

Union of languages L1 and L2 can be written as:

L1 = {x: x belongs to L and x is a}

L2 = {x:x belongs to L and x is b}

L1 U L2 = {x: x is in L1 or L2} = (a | b) or a,b or (a + b)

Concatenation can be written as:

L1 = {x: x belongs to L and x is a}

L2 = {x: x belongs to L and x is b}

L1. L2 = {ab | a is in L1 and B is in L2} = a.b

Kleene Closure of language L can we written as:

L^* = Zero or more occurrence of L.

Ways to design regular Expression:

1)      Directly from Language.

2)      From DFA/NFA.

Here I will be focussing on first method only.

e.g. Write a regular expression for the language
·       L = {ab}

Regular Expression: ab

·       L = {a|b}

Regular expresson = (a + b), The language states that either a is there or b is     there.

·       L = {ab^n: n>3}

RE = ab³

·       L = { wc: w belong to (a,b)^* } – This language indicates that w followed by ‘c’ or concatenated with c and w defines zero or more occurrences of a or b.

RE = (a+b)^* . c

·       L = { wc: w belong to (a,b)⁺ } – This language indicates that w followed by ‘c’ or concatenated with c and w defines one or more occurrences of a or b.

RE = (a+b)⁺.c

·       L = {w: w belongs to any combination of a,b and ends with a}

RE:

Step-1: RE for any combination of a,b = (a + b)^*

Step-2 : w always ends with a that means any combination of a,b followed/concatenated with a = (a + b)^*.a

–       Now come to our question #2. Regular language for End (L, a) ?

End(L,a ) = {x: x belongs to L and x is ended with symbol a}.

L is given as :

((aa+bbb)^*c)^*

Step-1: Language L is already given in Regular expression form. If not, first write its regular expression. Here no need to write regular expression for language L.

Step-2 : End(L,a) indicates that string belongs to language L and ended with symbol a.

So L will be concatenated with a.

RE = L.a

Step-3: Replace L with its regular expression

RE = L.a = ((aa+bbb)^*c)^*.a

Regular expression for End(L,a) = ((aa+bbb)^*c)^*.a