Computer theory , please solve just the questions that have marks

Derivation trees show which productions are used in obtaining a sentence, but do give the order of their application. Derivation trees are able to represent any derivation, reflection the fact that this order is irrelevant, an observation that allows us to close a gap in the preceding discussion. By definition, any w element L (G) has a derivation, but we have not claimed that it also had a leftmost or right most derivation. However, once we have a derivation tree, we can always get a leftmost derivation by thinking of the tree as having been built in such a way that the leftmost variable in the tree was always expanded first. Filling in a few details, we are led to the not surprising result that any w elementof L(G) has a leftmost and a rightmost derivation (for details, see Exercise 25 at the end of this section). 1. Complete the arguments in Example 5.2, showing that the language given is generated by the grammar. 2 Draw the derivation tree corresponding to the derivation in Example 5.1. 3. Give a derivation tree for w = abbbaabbaba for the grammar in Example 5.2. Use the derivation tree to find a leftmost derivation. 4. Show that the grammar in Example 5.4 does in fact generate the language described in Equation 5.1. 5. Is the language in Example 5.2 regular? 6. Complete the proof in Theorem 5.1 by showing that the yield of every partial derivation tree with root S is a sentential form of G. 7 Find context-free grammars for the following languages (with n greaterthanorequalto 0, m greaterthanorequalto 0). (a) L = {a^n b^m: n lessthanorequalto m + 3} (b) L = {a^n b^m: n notequaltom - 1} (c) L = {a^n b^m: n notequalto 2m} (d) L = {a^n b^m: 2n lessthanorequalto m lessthanorequalto 3} (e) L = {w elementof {a, b}*; n__b (w)}. (f) L = {w elementof {a, b}*; n_a greaterthanorequalto n_b(v), where v is any prefix of w}