0
$\begingroup$

L={⟨M⟩: M is a DFA and for each string in L(M) the number of 1s is more than or equal to the number of 0s }

T = "On input where M is encoded DFA"

1. Construct another DFA D such that L(D)={x|x has more or equal 1s than 0s}
2. For each input x
   a. if( x is accepted by DFA M){
          if(accepted by D){
           "accepted" and return;
          }
3. "rejected"

Is this proof true?

$\endgroup$
3
  • 1
    $\begingroup$ How do you construct $D$? $\endgroup$
    – Steven
    Commented Jul 4, 2021 at 15:32
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$
    – D.W.
    Commented Jul 5, 2021 at 7:11
  • $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W.
    Commented Jul 5, 2021 at 7:11

1 Answer 1

1
$\begingroup$

No, this proof is not correct. You can't iterate through all inputs $x\in \Sigma^*$ since it would take you "infinite time".

The correct way to do this is to construct the complement of $D$ (as a pushdown automaton! as @Steven mentioned), which we will call $D^c$, then construct the intersection PDA $D^c\cap M$ (notice that this can be done since $M$ is a DFA), and test if its language is empty. If it is, you can be sure that $L(M)\subseteq L(D)$, hence all words in $M$ have more $1$'s than $0$'s

$\endgroup$
1
  • 1
    $\begingroup$ @Steven thanks for the correction! $\endgroup$
    – nir shahar
    Commented Jul 4, 2021 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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