Search code examples
complexity-theorycontext-free-grammarautomatapushdown-automatoncontext-free-language

Some constraint on Language and CFG

I see one note about automaton theory:

Consider the following language:

L={xy : x,y in {a,b}*}

and consider following constraint:

1) x=y

2) x != y

3) x=(y)reverse

4) number of x is not equal to number of y

i read a language with constraint 2,3,4 is context free. any hint or tutorial for 1 to 3 is highly appreciated.

Solution

  • As you say, L1: {xy | x,y ∈ {a,b}* ∧ x=y} is not a context-free language.

    However, the very similar L3: {xy | x,y ∈ {a,b}* ∧ x=y-1} is context free, as follows:

    S → Ø
S → a S a
S → b S b

    Technically speaking, the two other languages in your question are trivial:

    L2: {xy | x,y ∈ {a,b}* ∧ x≠y}
    L4: {xy | x,y ∈ {a,b}* ∧ |x|≠|y|}

    because the only string which does not satisfy the constraint is the empty string. Any non-empty string S can be trivially decomposed into the two non-equal strings Ø and S; it's clear that the concatenation of these two strings is S and that unless S is empty, the two strings are unequal and have different lengths. The language consisting of all non-empty strings is not only context free, but also regular: (a|b)+.

    Since that was so easy, I suspect that it is not what you were actually asking, but I cannot guess what you really meant. I suggest you edit the question to be more precise.