recategorized by
4,123 views
4 votes
4 votes

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 by

5 Answers

Best answer
6 votes
6 votes

                     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 | ∈ .

edited by
1 votes
1 votes

Answer : B

               

edited by
0 votes
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
0 votes
0 votes
here  B is the correct answer it can generate all even length strings of palindrome
Answer:

Related questions

6 votes
6 votes
2 answers
1
go_editor asked Jul 13, 2016
9,628 views
The minimum number of states of the non-deterministic finite automaton which accepts the language$\{ a b a b^n \mid n \geq 0 \} \cup \{ a b a^n \mid n \geq 0 \}$ is3456
1 votes
1 votes
1 answer
4
shivani2010 asked Jun 18, 2016
824 views
Which of the following regular expression identifies are true?(r+s)*=r*s*(r+s)*=r*+s*(r+s)*=(r*s*)*r*s*=r*+s*