The Gateway to Computer Science Excellence
+4 votes
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$
in Theory of Computation by Veteran (105k points)
recategorized by | 903 views

5 Answers

+5 votes
Best answer

                     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 by
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...smiley

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

Answer : B

               

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

Tauhin Gangwar  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
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
by Boss (11k points)
0 votes
here  B is the correct answer it can generate all even length strings of palindrome
by (349 points)
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.
by (241 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,508 answers
195,524 comments
100,960 users