Я хочу регулярное выражение (теория автоматов)

Question

Рассмотрим алфавит V = {0, 1,…, 9} и язык L, который состоит из всех строк V, которые представляют все целые числа, которые больше 798 (например, строки 799, 890, 2345, 777777 принадлежат языку L, тогда как строки 1, 42, 711, 798 - нет). Предоставлять регулярное выражение, которое генерирует все строки языка L

Answer 1

Идет полностью классическое регулярное выражение (то есть дизъюнкция, конкатенация и клин-звезда):

(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)*)

Если вы разрешите типичные сокращения регулярных выражений (но оставайтесь в теоретических пределах, то есть на обычном языке), то это может быть уменьшено до:

799|[89]\d{2,}|[1-9]\d{3,}

Вы соответствуете либо номеру 799, трехзначному числу, начинающемуся с 8 или 9, либо четырех- (или более) -значному числу, начинающемуся с любой цифры, кроме 0 (чтобы запретить 0023 сопоставление).