1
$\begingroup$

What is the regular expression for language containg no. of 011 equal to 110 in string ?

$\endgroup$
3
$\begingroup$

Usually, languages of the form "The number of $x$s is equal to the number of $y$s" aren't regular because you could have an arbitrarily long sequence of $x$s with no $y$s but a finite state automaton can't remember how long that sequence was.

However, in this case, any time you see $011$, either the rest of the string contains only $1$s or the string looks like $0111^k0\ldots$ for some $k\geq 0$ and you've found the matching $110$. If you think about this for a bit, and try some examples, you should be able to figure out some simple rules that determine whether a string is in the language, and then implement that as a regular expression.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.