MCQ:

A) Five languages are defined by the following five grammars:

L1: S aaSa |

L2: S aSaa | a

L3: S aaA, A aS |

L4: S Saaa | aa |

L5: S aaA | a | , A aS

Determine:

1)Which pairs of languages are disjoint?

2)Which languages are contained in which other languages?

3) Which languages are complements of one another (with respect to the language a*)?

Then, identify the statement below that is FALSE.

a) L1 is contained in L5.

b) L1 and L3 are disjoint.

c) L1 and L2 are disjoint.

d) L2 is contained in L4.

-

B) The intersection of two CFL's need not be a CFL. Identify in the list below a pair of CFL's such that their intersection is not a CFL.

a) L₁={aⁿb^jcⁱc | n>0, i>0, j>0} L₂={a^jaⁿbⁱcⁱ | n>0, i>0, j>0}

b) L₁={abaⁿbⁿcⁱ | n>0, i>0} L₂={abaⁿb^jcⁱ | n>0, i>0, j>0}

c) L₁={acaⁿb^jcⁱc | n>0, i>0, j>0} L₂={aca^jaⁿbⁱcⁱ | n>0, i>0, j>0}

d) L₁={abaⁿbⁿcⁱ | n>0, i>0} L₂={abaⁿbⁱcⁱ | n>0, i>0}