Question

For context the class is about Automata, Computability, and Formal Languages

I just need parts b & e done

14. Find grammars for E = {a, b} that gener- ate the sets of (a) all strings with exactly two a's. (b) all strings with at least two a’s. (c) all strings with no more than three a's. (d) all strings with at least three a’s. (e) all strings that start with a and end with b. (f) all strings with an even number of b’s. In each case, give convincing arguments that the grammar you give does indeed generate the indicated language.

Answer 1

The grammars for = {a,b} that generates the sets of (a) All strings with exactly two a's SAAA aAaAaAa A DATE The regular expression for the language having exactly two a's is (b+c)a(b + c)(b + c)* The strings generated by the grammar that has exactly two a's are: aa, aab, baa, bbaa, ababa, baba, baab (b) All strings with at least two a's S AaaAaAaAaAa A abAE The regular expression for the language having at least two a's is (a+b)*a(a+b)*a(a+b)* The strings generated by the grammar in which the strings have at least two a's are aa, baa, aab, bbaa, aabb, baab, abab, baba, aaabb......etc

(c) All strings with no more than three a's S3 AaaAaAaAAAAAAAQA a Aa AaaaAaAaAaAAAAAAA A3 A4 € The regular expression for the language having all strings with no more than three a's is (b + c)*a(b+c)*a(b + c) *a[b+c)* The strings generated by the grammar in which the strings have no more than three a's are: aa, aab, baa, bbaa, aabb, baab, abab, baba, baab, aaa, a, ba, ab, bab, aba, baaa, aaab.... (d) All strings with at least three a's S3 AaaaAaAaAaAAaAaAa A abAle The regular expression for the language in which all strings have at least three a's is b*ab*ab*a(a+b)* The strings generated by the grammar in which the strings have at least three a's are: aaa, aaab, baaa, bbaaa, aaabb, baaab, ababa, abaab, aaabba.... (e) All strings that start with a and end with b

Sab A aAAa| bA|Able The regular expression is a(a+b)*b The strings generated by the grammar in which all strings start with a and end with b are ab, aab, aabb, aaabbb, aabb, abab, abbabababb....etc (f) All strings with an even number of b's SaSA A abs The regular expression is a(bb) a The strings generated by the grammar in which the strings have an even number of b's are a, bb, abb, bba, baab, abba, aabb....