Theory of Computation: Describe a CFG for the following languages:

2. Describe a CFG for the following languages: Note: w denotes flipping every bit in the string w, for example: 00101 11010 (b) (we {a,b)* | num(a,w)= num(b, w)) Hint: Consider the following example where we graph num(a, w) - num(b, w) for all prefixes of w: 2 0 -1 Imagine breaking up the string into pieces every time the graph crosses the x-axis. Look at the first and last character of each such piece and think recursively