A string y is a prefix of x if there exists a string z with

A string y is a prefix of x if there exists a string z with x = yz. For x {0, 1}*, let #(a, x) be the number of occurrences of the symbol a in the string x. Define L = {x | #(0, y) lessthanorequalto #(1, y) + 1 for all prefixes y of x}. Give an argument, why this language L is not regular, or draw a transition diagram of an FA (finite automaton) accepting L. Define L\' = L {x | #(1, y) lessthanorequalto #(0, y) +1 for all prefixes y of x}. Give an argument, why this language L is not regular, or draw a transition diagram of an FA (finite automaton) accepting L\'. Present a transition table for the FA given in (a) or (b) above. Remember to mark the start state with an rightarrow and all accepting states with a *.

Solution

It is easy to see that any string in A must start with a 1, and contain at least one other 1 (in the matching y segment). Conversely, any string that starts with a 1 and contains at least one other 1 matches the description for k = 1. Hence, A is described by the regular expression 1 0 1 (0 1) , and is therefore regular.

(b) Assume to the contrary that B is regular. Let p be the pumping length given by the pumping lemma. Consider the string s = 1p0 p1 p B. The pumping lemma guarantees that s can be split into 3 pieces s = abc, where |ab| p. Hence, y = 1ⁱ for some i 1. Then, by the pumping lemma, ab² c = 1^p+i⁰ p¹ p B, but cannot be written in the form specified, a contradiction.

(c) Consider any two different k-bit strings x = x1 . . . xk and y = y1 . . . yk and let i be some position such that xi 6= yi (there must be at least one). Hence, one of the strings contains a 1 in the ith position, while the other contains a 0. Let z = 0ⁱ¹ . Then z distinguishes x and y as exactly one of xz and yz has the kth bit from the end as 1. Since there are 2k binary strings of length k, which are all mutually distinguishable by the above argument, any DFA for the language must have at least 2^k states.