Programming Languages and Compilers

OCaml Programming

In the following, you will be given a description of a regular language over a given alphabet and you will be asked to give first a regular expression and then a right regular grammar generating that language. The alphabet of the language is given as a part of the problem statement. When writing a regular expression, in addition to the alphabet given, you may use the symbols $(,),$ E$,$ V$,*,+$ for, respectively, grouping, epsilon, or$,$ Kleene star, and Kleene plus. Other symbols will either cause a parse error or will not be interpreted as you intend.

When writing right regular grammars, terminals will always be single non$-$uppercase letters, digits, or symbols. Nonterminals are identifiers starting with an upper case letter. The separator for rules between the left$-$hand nonterminal and the right$-$hand string is ::$=.$ The empty string may be represented by epsilon. You may use the extended CFG construct $|$ to compactify rule representation. You may use, or not use, white space $($space$,$ tab, newline$)$ freely; they will not alter the meaning of your rules, except when you run a nonterminal into a terminal or other nonterminal, creating a nonterminal of a longer name. You must either begin or end your grammar with a declaration of its start symbol with Start Symbol $=$ nonterminal.

Problem

Consider the set of all strings over the alphabet $,$