0
State and Explain closure properties of Context Free Language.

Mumbai university > Comp > SEM 4 > TCS

Marks: 5M

Year: May 2015

0  upvotes
0

Context-free languages are closed under union, concatenation, and Kleene star.

Suppose G1 = (V1,1,R1, S1) and G2 = (V2,2,R2, S2).

S1 → aS1b

S1 →ǫ

For G2 we have

S2 → cS2d

S2 →ǫ

Then L (G1) = ${a^n b^n: n ≥ 0}$. Also, L (G2) = ${c^n d^n: n ≥ 0}$

1) Union

G = (V1 ∪ V2 ∪ {S},∪_1 ∪_2, R, S) where R = R1 ∪ R2 ∪ {S → S1, S → S2} and S is a new symbol.

Then L (G) = L (G1) ∪L (G2).

Example:

S1 → aS1b

S1 → ǫ

S2 → cS2d

S2 → ǫ

S → S1

S → S2

Then L (G) = ${a^n b^n: n ≥ 0} \ \ ∪ \ \ {c^n d^n: n ≥ 0}$

2) Concatenation

G = (V1 ∪ V2 ∪ {S},∪_1 ∪_2, R, S) where R = R1 ∪ R2 ∪ {S → S1S2} and S is a new symbol.

Example:

S1 → aS1b

S1 → ǫ

S2 → cS2d

S2 → ǫ

S → S1S2

Then L(G) = ${a^n b^n c^n d^n: m, n ≥ 0}$

3) Kleene star

G = (V1 ∪ {S}, ∪_1, R, S) where R = R1 ∪ {S → ǫ, S → SS1} and S is a new symbol.

Example:

S1 → aS1b

S1 → ǫ

S → ǫ

S → SS1

Then L(G) = ${a^n b^n: n ≥ 0}$

4) Non-closure properties

Context-free languages are not closed under intersection or complement.

0  upvotes
Please log in to add an answer.

Next up

Read More Questions

If you are looking for answer to specific questions, you can search them here. We'll find the best answer for you.

Search

Study Full Subject

If you are looking for good study material, you can checkout our subjects. Hundreds of important topics are covered in them.

Know More