Consider the alphabet V={0, 1, …, 9} and the language L, which consists of all strings of V, which represent all integers that are greater than 798 (for example, the strings 799, 890, 2345, 777777 belong to the language L, whereas the strings 1, 42, 711, 798 do not). Provide a regular expression that generates all strings of the language L
Going completely classic regular expression (i.e. disjunction, concatenation, and kleene star):
(799|(8|9)(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*|(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*)
If you allow typical regex shorthands (but stay within the theoretical limits, i.e. a regular language), that can be reduced to:
799|[89]\d{2,}|[1-9]\d{3,}
You match either the number 799, a three digit number starting with 8 or 9, or a four- (or more) -digit number starting with any digit but a 0 (to disallow 0023 matching).