CODEWITHSUNDEEP
regexregular-languageformal-languagescontext-free-language
Lilith X
Lilith X

Reputation: 99

Are there any languages such that they are proper subsets of each other and satisfy these conditions

Are there languages such that A ⊂ B ⊂ C ⊂ D ⊂ E over the alphabet {a,b,c} where:

A is not context-free

B is context-free and non-regular

C is regular

D is non regular

E is regular and not {a,b,c}*

Upvotes: 2

Views: 278

Answers (2)

Patrick87
Patrick87

Reputation: 28292

First, let us simplify this and take care of E by just not using c in any language and making E the language (a + b)*. Next, let us deal with D by making it the same as E, but with all strings of prime length greater than two removed. We can choose C to be the set of all even-length strings over {a, b}: (aa + ab + ba + bb)*. For a context-free and non-regular language we can choose the set of even-length palindromes over {a, b}: S -> aSa | bSb | e. Finally, we can choose as A the set of even-length palindromes over {a, b} which begin with a prime number of as.

We might have tried getting rid of D by making it the union of C and some language involving only b, then making C equal to a* and then trying to find A and B using only a... but we might have had trouble finding a context-free non-regular language involving only one symbol.

Upvotes: 1

f9c69e9781fa194211448473495534
f9c69e9781fa194211448473495534

Reputation: 4620

Start by taking non-context-free language A over {a,b}. For example A = { ww | w \in {a,b}*}, but any other would also work.

You can then build the other languages on top of that:

  • B = {a,b}* U {a^i c^i | i >= 0}
  • C = {a,b}* U {a,c}*
  • D = {a,b}* U {a,c}* U {b^i c^i | i>= 0}
  • E = {a,b}* U {a,c}* U {b,c}*

You can then verify for each of these that they have the desired properties.

Upvotes: 2

Related Questions