The Gateway to Computer Science Excellence
+2 votes
509 views
in Theory of Computation by Junior | 509 views

3 Answers

+3 votes
Best answer
regular .. look at it this way: we have, x wwr y . x and y can expand from both ends.. only thing required is 00 or 11 in the middle.. which is nothing but the smallest string in wwr. So the language ultimately comes down to, "language containing 00 or 11 as substring"
by Active
selected by
0 votes
regular language bcz X and Y are expanded to both sides
by
0 votes

This language is regular since we have flexibility in choosing x and y we can convert it to set of strings containing 00 or 11 as substring.

suppose x=110001, y=100011, w=0110, w^r=0110, w=011, w^r=110

then XWW^rY = 11000101100110100011 or 1100010111100100011.

so REGULAR EXPRESSION is = (1+0)*(00)(1+0)* + (1+0)*(11)(1+0)*

by
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
52,218 questions
59,876 answers
201,072 comments
118,119 users