The Gateway to Computer Science Excellence

+3 votes

+11 votes

Best answer

WXW^{R }is regular on {a,b} .** X can be anything** .

so we can rewrite this language as** " starting bit and ending bit are same "** which is a regular language .

Here, If alphabet set = (a,b)^{+},

Then , Language accepted by the finite automata, ** L = a(a+b) ^{+}a + b(a+b)^{+}b .**

see this : http://stackoverflow.com/questions/14521300/why-l-wxwr-w-x-belongs-to-a-b-is-a-regular-language

0

According to you if W=101 X=100 then W^R=101

The string is 101100101

but if i pass the string 10**0**100101 which starts and ends with but doesn't follow the language.

0

Always only first character will be considered for W and if this string ends with same character then it should be accepted and otherwise rejected.

In your above 1st example you can assume like - W = 1, X = 0110010, W' = 1.

And in your 2nd example- L= 100100101, W = 1, X = 0010010, W'= 1.

In your above 1st example you can assume like - W = 1, X = 0110010, W' = 1.

And in your 2nd example- L= 100100101, W = 1, X = 0010010, W'= 1.

0

yes, you can,** but not necessary**. You can also take W as 10 but In every case first charecter must have to match with last character of string to get accepted by the FA, then only we can get W and W'.

0

if your question was in the category which says x is bounded.. then |x|=3, so its not regular..

but the question says x is unbounded , we can treat this entire language as starting and ending with same symbol.. then we will assume w and reverse of w as the first and last symbol. so here w=1(fst) and w^r =1(last symbol)..remaining all will be x ..in this language its not saying what is x or how many symbols are x ..so we have the provision to make everything except first and last to be x.. but if it was given that |x|=3' then it will not be regular..here w is not given or length of w or x is not given..so we can assume this way

but the question says x is unbounded , we can treat this entire language as starting and ending with same symbol.. then we will assume w and reverse of w as the first and last symbol. so here w=1(fst) and w^r =1(last symbol)..remaining all will be x ..in this language its not saying what is x or how many symbols are x ..so we have the provision to make everything except first and last to be x.. but if it was given that |x|=3' then it will not be regular..here w is not given or length of w or x is not given..so we can assume this way

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,648 questions

56,459 answers

195,337 comments

100,192 users