The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+2 votes
in Theory of Computation by Junior (755 points) | 371 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 (2.3k points)
selected by
0 votes
regular language bcz X and Y are expanded to both sides
by (365 points)
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 (111 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,309 questions
55,743 answers
90,497 users