correct explaination...

in (c) option shrama why u went for baaa...u shud check minimum string only "ba" which also not even length palindrome....but it has no concern ...ur one is also correct...we only need 2 prove it is not even length...

The Gateway to Computer Science Excellence

+4 votes

Which of the following definitions generates the same Language as $L$, where $L=\{ WW^R \mid W \in \{a, b\}$*$\}$?

- $S \rightarrow asb \mid bsa \mid \in$
- $S \rightarrow asa \mid bsb \mid \in$
- $S \rightarrow asa \mid bsa \mid asa \mid bsb \mid \in$
- $S \rightarrow asa \mid bsa \mid asa \mid bsb \mid$

+6 votes

Best answer

L={WW^{R}∣W∈{a,b}*}.

This Language accepts Even length of palindrome.

The set of strings generated by L ={∈,aa,bb,abba,baab,bbbbbb,bbaabb....}

(A)Due string ab(S->aSb->ab) we can eliminate this option because this is not even length palindrome.

(B)In this option accepts all even length palindrome. Ex:-∈,aa,bb,aaaa,abba,baab,bbbb etc.

(C)Due to string baaa (S->bSa->baSaa->baaa) we can eliminate this option because this is not even length palindrome.

(D)In option D we can not able to generate any string because to stop repetition S

there is no terminal symbol present.

Hence,Option**(B)aSa | bSb | ∈** .

0

correct explaination...

in (c) option shrama why u went for baaa...u shud check minimum string only "ba" which also not even length palindrome....but it has no concern ...ur one is also correct...we only need 2 prove it is not even length...

+1 vote

0 votes

A .IS WRONG WE CANT GENERATE aa.

D.IS WRONG WE CANT GENERATE ANY TERMINAL

C. IT GENERATES ab,ba WHICH IS NOT SAME AS THE LANGUAGE

AND B GENERATES ALL STRINGS ..

SO B IS THE ANS

D.IS WRONG WE CANT GENERATE ANY TERMINAL

C. IT GENERATES ab,ba WHICH IS NOT SAME AS THE LANGUAGE

AND B GENERATES ALL STRINGS ..

SO B IS THE ANS

0 votes

Given question generates Even length palindrome.

Option a doesn't generates even length palindromes and thus eliminated.

Option b is correct generating even length palindromes.

Option c is also generating string abaa and thus eliminated.

Option d their is no terminal symbol present to stop repetition of S.

Option a doesn't generates even length palindromes and thus eliminated.

Option b is correct generating even length palindromes.

Option c is also generating string abaa and thus eliminated.

Option d their is no terminal symbol present to stop repetition of S.

52,375 questions

60,571 answers

201,973 comments

95,387 users