I have drawn the DFA for language L1 containing strings starting with 01 and language L2 containing strings ending in 11. For the final DFA, I have concatenated both DFA's. The finals DFA does not accept 011. Kindly help!


The reason why your DFA doesn't work is that not all strings that start with 01 and end with 11 can be written as a concatenation of a string $x$ that start with 01 and a string $y$ that ends with 11, as you discovered.

This can happen because $x$ and $y$ might intersect. However the only way for this to happen is for $x$ and $y$ to share a single "$1$". I.e., the only problematic string is $011$. To fix this you can just union your DFA with one that recognizes $011$.

Rephrasing your problem using a regular expression, you cannot obtain a regular expression for you language by simply concatenating $01(0\mid1)^*$ with $(0\mid1)^*11$ which would yield $01(0\mid1)^*(0\mid1)^*11=01(0\mid1)^*11$. However, the following regular expression is correct:

$$ ( 01(0 \mid 1)^*11 ) \mid (011) $$

  • $\begingroup$ Thank you! That is very helpful! $\endgroup$ Jun 26 '21 at 4:27

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.