Question

Theory of computation:

Consider the alphanumeric alphabet Σ = {a, b, . . . , z, A, B, . . . , Z, 0, 1, . . . , 9} and let L be the language of all regular expressions over Σ:

L = {w ∈ Σ ∪ {∅,(,), ∪, ·, * }* | w is a syntactically legal regular expression over Σ}

Give an unambiguous context-free grammar that generates L. The grammar should use the following precedence levels, from highest to lowest:

(1) * (Kleene star) – highest precedence

(2) · (concatenation)

(3) ∪ (union) – lowest precedence

Answer 1

the context free language is defined by a context free grammar represented in the form of a 4-tuple (V, T, P, S) where

V = set of non terminal symbols

T = set of terminal symbols

P = set of production rules

S = starting symbol

the higher the precedence, the later it comes in the production

for example

S is starting symbol

so we start with the operator of lowest precedence i.e. union

then in the next rule we take up concatenation

and at the end we take up kleene star because of highest precedence

this is done because whenever an expression is given, if we think logically first the highest precedence operation is performed which means first the production corresponding to the highest precedence operator is used to reduce the expression in bottom up approach