iii. Given ={a,b}, write a CFG for the language L={ww is not a palindrome }, the language of strings that are not the same when read forwards and backwards. For example, aab L and baabab L, but aba /L, bb /L, and /L. v. Suppose that we want to check whether x+y=z, where x,y, and z are all natural numbers. If we want to phrase this as a problem as a question of strings and languages, we will need to find some way to standardize our notation. In this problem, we will be using the unary number system, a number system in which the number n is represented by writing out n1 's. For example, the number 5 would be written as 11111 , the number 7 as 111111 , the number 12 as 11111111111 , and the number 0 as . Given the alphabet ={1,+,=}, we can consider strings encoding x+y=z by writing out x,y, and z in unary. For example: 4+3=77+1=80+1=1wouldbeencodedaswouldbeencodedaswouldbeencodedas1111+111=11111111111111+1=11111111+1=1 Consider the following language, which we'll call ADD : {1m+1n=1m+nm,nN} For example, the strings 111+1=1111 and +1=1 are in the language, but 1+11=11 is not, nor is the string 1+1+1=111. Write a CFG for ADD. You may find it easier to solve this problem if you first build a CFG for this language where you're allowed to have as many numbers added together as you'd like. Once you have that working, think about how you'd modify it so that you have exactly two numbers added together on the left-hand side of the equation. v. Let be an alphabet containing these symbols: N{}, We can form strings from these symbols which represent sets. Here's some examples: 0 - {{N,}{}} {,{,{}}} - {,N}N - N{N,} - {{{{N}}}} - {{}} - {}N{N} \{\} - N - {,,} - {N} - {,{}} Notice that some of these sets, like {,}, are syntactically valid but redundant, and others like \{\} are syntactically valid but not the cleanest way of writing things. Here's some examples of strings that don't represent sets or aren't syntactically valid: o N ,,{} 0{ 0}{ {,N} }}N {N} - N, - {,,, {{} {, - {N,,} Write a CFG for the language {ww is a syntactically valid string representing a set \}. Please use the letters n,u, and o in place of N,, and , respectively. Fun fact: the starter files for Problem Set One contain a parser that's designed to take as input a string representing a set and to reconstruct what set that is. The logic we wrote to do that parsing was based on a CFG we wrote for sets and set theory. Take CS143 if you'r curious how to go from a grammar to a parser! As a hint, as is often the case when writing CFGs, we recommend that you use different nonterminals to represent different components of the string. For example, structure of a comma-separated list of sets is different than the structure of an expression representing a single set