0% found this document useful (0 votes)
6 views2 pages

DFA for Binary Strings with Constraints

The document describes a language consisting of strings over the alphabet {0,1} where every substring of three symbols contains at most two zeros. Examples of valid strings are provided, while an invalid example is given to illustrate the rule. Additionally, there is a reference to a partially completed DFA that accepts this language, with missing arcs indicated.

Uploaded by

jinitha.A
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
6 views2 pages

DFA for Binary Strings with Constraints

The document describes a language consisting of strings over the alphabet {0,1} where every substring of three symbols contains at most two zeros. Examples of valid strings are provided, while an invalid example is given to illustrate the rule. Additionally, there is a reference to a partially completed DFA that accepts this language, with missing arcs indicated.

Uploaded by

jinitha.A
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

1.

Consider the set of strings on {0,1} in which, every substring of 3 symbols has at
most two zeros. For example, 001110 and 011001 are in the language, but 100010 is not. All
strings of length less than 3 are also in the language. A partially completed DFA that accepts
this language is shown below.

The missing arcs in the DFA are


 A

You might also like