We say that a string x is proper if each prefix of x has at most one more 0 than

ID: 3679655 • Letter: W

Question

We say that a string x is proper if each prefix of x has at most one more 0 than 1 and at most one more 1 than 0. Show by induction on the length of the string that the following 4 conditions hold

(a) ?(q0, x) = q0 if and only if x is proper and contains the same number of 0 and 1

(b) ?(q0, x) = q1 if and only if x is proper and contains one more 0 than 1

(d) ?(q0,x)=q3 ifandonlyifxisnotproper

Explanation: The base of the induction are string of size 1 and then you show directly that all the above properties hold (for example q3 can not be involved in strings of length 1). Show that if all 4 properties hold for all strings of size i they hold for all strings of size i + 1.

After i + 1 letters of course you can switch state. For example you may be in q1 after i characters and a 0 comes and then you move to q3. Use in this case the induction hypothesis and the fact that the next char is 0 to prove the inductive assumption over q3.

0 a1 1 0 1 0) 3 an 0

Explanation / Answer

Solution for L1:

first write a NFA that accepts the complement of L1, transform it into a DFA, exchange accepting / nonaccepting states.

derive regex from your DFA or build regex directly from admissible concatenations of non-101 three-symbol words (taking care of leading two- and one-symbol words and the empty word) One solution for L2:

The words of even length must have identical numbers of 1's and 0's. The rest is easy. design a DFA A1 whose states count the number 0's read in and accepts all words with 3n zeros, and another similar DFA A2 accepting words with 5n zeros. Join A1 and A2 in a NFA. (c): create regex from your NFA or write down directly, as ((1*01*)3 )+ |((1*01*)5 )+

Q =
[
1i<m
Qi {q0} {qai
| Ai = }
where q0, qa1
, . . . , qam are all mutually distinct and also different from each state in
S

(q0, x) = q0 if and only if x is proper and contains the same number of 0 and 1
Qi
F =
[
1im
Fi and is defined as follows :
for every qi Qi
, (qi
, a) = i(qi
, a) for each a
(q0, ai) = (
q0 if Ai 6=
qai
if Ai =
and (qai
, a) = qai
for all a .

Thus from the above. the following condition holds

(q0, x) = q1 if and only if x is proper and contains one more 0 than 1

((q0, x) = q2 if and only if x is proper and contains one more 1 than 0

((q0,x)=q3 ifandonlyifxisnotproper

Navigate

We say that a fatty acid is saturated when A. It does not admit more carbon B. I

We say that a value \"is everywhere\" in an array of integers if, for every pair

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

We say that a string x is proper if each prefix of x has at most one more 0 than

Question

Explanation / Answer

Related Questions

Navigate