1
$\begingroup$

I am trying to make the DFA and RE of a regular language which is define on the alphabet = {1,0} and all the strings present in these languages have exactly one 010 substring in them.

Some strings which are accepted by the above regular language are;

{010, 0100, 0101, 1010, 0010 .......0101110.....}

In the above strings there is only one 010 substring. If there is more than one 010 substring in a string such as.

{01010, 01011010... }

then the DFA of the above language should not accept that string.

If someone provide me ony DFA of the above lang. then i would be able to make the RE by state elimination. Or if someone provide me the RE of the above lang. then i could make the DFA by other kleene theorem.

My work: I made the following DFA for that language;

enter image description here

This DFA is accepting all the strings like 010, 0100, 0101, 1010, 0010.... and its also rejecting the string with more than 010 like 01010. But with that its rejecting 0101110 string which is part of the language.

Note: I go through the question which is already on the CS stackexchange as previously my question was marked duplicate. This question is about "How we can prove that a given language is regular or not". But in my question i have provided the descriptive definition of a regular language. And i am trying to get its RE or DFA.

Improve this question
$\endgroup$
  • $\begingroup$ Please don't delete and re-ask your question. That question contains general techniques that suffice to enable you to construct such a DFA. See, e.g., cs.stackexchange.com/a/11051/755. I was hoping you would study those techniques, try applying them to your problem, and then show us your attempts and where you got stuck. We discourage questions that are the statement of an exercise-style problem (find a DFA for this regular language) with a request for someone to solve the exercise for you. $\endgroup$ – D.W.♦ Mar 8 '19 at 18:48
  • $\begingroup$ I added my work and also added that where i stuck. Please remove your downvote Sir if you think question is valid now! $\endgroup$ – Zeeshan Ahmad Khalil Mar 9 '19 at 8:48
3
$\begingroup$

You can always use the current state of the automaton to remember the last three characters you've seen. Now, you can implement two phases. In the first phase, you're happy if you're ever in the situation where the last three characters were $010$. In the second phase, you become unhappy if you ever see $010$ again.

Improve this answer
$\endgroup$
  • $\begingroup$ I am getting problem in second phase sir $\endgroup$ – Zeeshan Ahmad Khalil Mar 9 '19 at 8:06
  • $\begingroup$ The two phases are very similar so, if you can do the first, you should be able to adapt it to do the second. Both of them are looking for $010$ and they only differ in how they react to that. $\endgroup$ – David Richerby Mar 9 '19 at 10:19
  • $\begingroup$ Thanks for your guidance! i just solved problem in second phase and made final DFA. If you think question is valid, please upvote. $\endgroup$ – Zeeshan Ahmad Khalil Mar 9 '19 at 10:41
2
$\begingroup$

Here's a hint; your language is, more or less, the concatenation of three languages: the strings not containing 010, the language consisting of the single string 010, and the strings not containing 010.

  1. Can you make a DFA which accepts all and only those strings not containing 010, perhaps as the complement of something?
  2. When I said "more or less" above, I was referring to the fact that the concatenation of the languages is a bit more complicated than vanilla concatenation. You have to deal with that.
Improve this answer
$\endgroup$
  • 1
    $\begingroup$ I don't think this is a good approach since, as you say, the concatenation part is complicated. $\endgroup$ – David Richerby Mar 8 '19 at 16:41

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.