# What is the regular expression for the following language?

What is the regular expression for the following language?
$$L = \{acbc: a,b,c \in \{0,1\}^+ \}$$ maybe we can say $$L = ((0 + 1)^+ 0 (0 + 1)^+ 0) + ((0 + 1)^+ 1 (0 + 1)^+ 1)$$ Is it true??

• Hint: it's something of a "trick" question. See if you can work out how to make almost any string be in the language. – David Richerby Nov 8 '18 at 13:42
• Hint: you can assume $|c|=1$ (why?). – Yuval Filmus Nov 8 '18 at 17:22
• Welcome to Computer Science! We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out these hints, or use the search engine of this site to find similar questions that were already answered. – Raphael Nov 8 '18 at 17:49
• Try to prove my hint. – Yuval Filmus Nov 9 '18 at 4:38
• That isn't a hint- it doesn't satisfy the specification of the language. It could be placed as an additional constraint on the language, but then no proof would be. required. And unless this constraint is applied, the language is not regular, and therefore cannot be expressed as an RE – Brishna Batool May 23 at 6:48

## 2 Answers

I claim that $$L$$ is equal to the set of all strings of the form $$a\gamma b\gamma$$, where $$a,b \in \{0,1\}^+$$ and $$\gamma \in \{0,1\}$$. Indeed, a string of this form clearly belongs to $$L$$. Conversely, if $$acbc \in L$$ and $$c=d\gamma$$, then $$acbc = ad\gamma bd\gamma$$ belongs to the new set. The new set is clearly described by the regular expression $$(0+1)^+0(0+1)^+0 + (0+1)^+1(0+1)^+1.$$

The question seems a bit less detailed. Note that, you have defined, a, b and c belong to {0,1}+ . Here, there is no upper bound for the length of c. We know that, regular expressions can only express regular languages, i.e. languages which are recognized by any Finite State Machine, like DFA. Finite State Machines have finite memory. To recognize the above language, machine needs to store the contents of first 'c' to match with the second 'c'. As the length of 'c' can be infinite, a Finite State Machine can not recognize this language.
However, if we introduce an upper bound to the length of 'c', then it will be regular language and can be expressed by a RE. For |c| = 1, your RE is correct.

• I agree. The language specified is not regular, and the regular expression provided is incorrect, unless |c| = 1 is imposed as an additional constraint. – Brishna Batool May 23 at 6:43