Context free grammar and pda for given language

Question

I have a context free language for which I have to create a context free grammar as well as pushdown automata either deterministic or non-deterministic. I have tried with different production rules and simulate them using jflap but unfortunately unsuccessful.

Any kind of guideline is appreciated.

L = { s1@s2@s3@…@sk | k > 1
       ∧ si ∈ {0,1}*
       ∧ ∃i,j i≠j ∧ si=sjR
     }

Examples of strings in L are: {01@10, 110@11111@011, ...}

Answer 1

The formal definition is a little hard to parse but here is what I got from it:

• This language is of the form s1@s2@s3...@sk
• Each of the si is a string of 0 and 1
• There is at least one pair of si, sj such that si = sj^R

Assuming this is the language, our strategy will be to enforce the 3rd condition first, then the 1st, then the 2nd. To enforce the 3rd we will require the entry of at least a pair of strings which are each others' reverses:

S -> 0S0 | 1S1

This gives us strings of the form wSw^R. Now, we want to be able to add other strings to the front, middle or back, all separated by @:

S -> 0S0 | 1S1
S -> T@S | S@T | @T@ | @

Finally, we need to allow T to generate strings of 0 and 1:

S -> 0S0 | 1S1
S -> T@S | S@T | @T@ | @
T -> 0T | 1T | e

To generate any string in the language:

1. first generate the pair of required reverse strings using the productions on the first line.
2. add any other strings to the left using the first production on the second line.
3. add any other strings to the right using the second production on the second line.
4. add any other strings to the middle using the third and fourth productions on the second line.
5. fill in the other strings using the productions on the third line.

A PDA for this language could do the following:

1. read (0+1)*@ in a loop
2. nondeterministically jump to a state where you assume you have found the first of the strings required by the 3rd condition
3. when you jump, push the string on the stack
4. read (0+1)*@ in a loop again
5. nondeterministically jump to a state where you assume you have found the second of the strings required by the 3rd condition
6. when you jump, pop the string off the stack to verify
7. read (0+1)*@ in a loop again

You make two nondeterministic guesses here: first, you guess about the string that will have a reverse. Second, you guess that you found it. If both of those guesses were right (and they will be for any string in the language, at least for one pair of k(k+1)/2 guesses) then the NPDA accepts.