Consider the language L = {w|w {0, 1}*, #0 (w) = #1 (w)}, here #30(w) and...

 

Transcribed Image Text:

Consider the language L = {w|w {0, 1}*, #0 (w) = #1 (w)}, here #30(w) and #1(w) means the numbers of Os and 1s in w respectively. That is, this is the language consisting of all strings with as many 1s as 0s: for example, 1010 L, 01101 & L. In this problem we will show how to construct a context-free grammar for it. 1. (8 points) For a length n word x, we define a function f (i) = (number of Os in locations [1...i]) (number of 1s in locations [1...]). Show that we have f(i) = f(j) for some i < j if and only if the substring in indices [i + 1, . . . j] has as many 1s as Os (i.e. Xi+1,i+2,... EL). 2. (8 points) Show that if x E L starts with 0, then it can be written as x = Owly where w, and y are each strings with as many 1s as Os (aka. w, y L). 3. (8 points) Give a context free grammar for this language L. Consider the language L = {w|w {0, 1}*, #0 (w) = #1 (w)}, here #30(w) and #1(w) means the numbers of Os and 1s in w respectively. That is, this is the language consisting of all strings with as many 1s as 0s: for example, 1010 L, 01101 & L. In this problem we will show how to construct a context-free grammar for it. 1. (8 points) For a length n word x, we define a function f (i) = (number of Os in locations [1...i]) (number of 1s in locations [1...]). Show that we have f(i) = f(j) for some i < j if and only if the substring in indices [i + 1, . . . j] has as many 1s as Os (i.e. Xi+1,i+2,... EL). 2. (8 points) Show that if x E L starts with 0, then it can be written as x = Owly where w, and y are each strings with as many 1s as Os (aka. w, y L). 3. (8 points) Give a context free grammar for this language L.