-3
$\begingroup$

How can design this question if we have an equation like that ={wxw | w={0,1}* , x=00} accept 00 it means not contain 000,001,100, but accept all these {00,1001,110011,001000001.....}. Thank you for helping me.

$\endgroup$
  • 1
    $\begingroup$ What have you tried? Where did you get stuck? $\endgroup$ – dkaeae Jan 3 at 16:02
  • 1
    $\begingroup$ Bad English, which is irritating but understandable on the ground of second language. Misleading question, since there is no DFA accepting a non-regular language. No sign of work shown, which is not welcomed on this site. $\endgroup$ – Apass.Jack Jan 4 at 5:11
0
$\begingroup$

as said above the language is non-regular , since there is no way a Finite automata can compare the existence of two same string in a single compound string. which is the case here. its is advised that please show the efforts that you made apart from asking questions.

$\endgroup$
0
$\begingroup$

After processing k 1’s in a row, the shortest string that would be accepted is 00, followed by k 1’s. This shows that after processing k 1’s or k’ 1s for k != k’, we are in different states. Which means there is an infinite number of states, therefore no DFA.

In general for any prefix u there is a set of suffixes v such that uv is in the language. Each such set is a state; if there are infinitely many different sets of suffixes leading to an accepted string then there is no DFA.

$\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.