903 views

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

1. $S \rightarrow asb \mid bsa \mid \in$
2. $S \rightarrow asa \mid bsb \mid \in$
3. $S \rightarrow asa \mid bsa \mid asa \mid bsb \mid \in$
4. $S \rightarrow asa \mid bsa \mid asa \mid bsb \mid$

recategorized | 903 views

L={WWR∣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 | ∈ .

by Boss (41k points)
edited
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...

0
@leen in option A total length of palandrom which is ab is even which is 2

similerly baaa here also length of palandrom is 4 which is even.
0
@worry but it is not palindrome
0
@tauhin can you explain little bit what kind of string we call as palandrom .
0
@worry i will not explain what is palindrome...google it out...and  learn dear
+1 vote

by Boss (45.3k points)
edited
0

@chauhan ...the above language doesn't generate....even no of a's and even no of b's ...

it cannot generate "abab"...which is even no. of a's and even no of b's ...//it only generates subset of it..

0
@tauhin do you have any idea what exactly it is generating  ? the question language
0
yes i have an idea....it generates the even palindrome
0

what's wrong with this explanation?It is also right .

0
it is right now...but before it was not...chauhan edited it after i told him...the error
0
ok
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
by Boss (11k points)
here  B is the correct answer it can generate all even length strings of palindrome
by (349 points)
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.
by (241 points)