Если грамматика G остается и правильно регулярно, почему $ || l (g) ||\ leq || p || $?

Question

Я изучал теорию автоматов и формальных языков и наткнулся на этот вопрос:

Если грамматика $ g $ остается влево и правильно, почему $ || l (g) || \ leq || p || $ ?

Я искал теорию, но я что-то упускаю. И я не могу найти ответ в любом месте, поэтому я спрашиваю здесь.

Определения:

$ p $ = Набор правил

Правое регулярное правило: грамматика $ g= (n, t, p, s) $ , правило в $ P $ Если правило в форме: $ a \ prightarrow ba $ $ (A, B \ in n) \ клин (a \ in t) $

Левое регулярное правило: грамматика $ g= (n, t, p, s) $ , правило в $ P $ Если правило в форме: $ a \ prumearrow ab $ $ (A, B \ in n) \ клин (a \ in t) $ .

Левая регулярная грамматика: грамматика, где все правила - регулярные правила.

Правая регулярная грамматика: грамматика, где все правила являются правильными правилами.

Пример набора правил $ p $ с обоими левыми и правильными правилами: $ p={a \ prevarrow a, b \ prightarrow b \} $

и быть как левым регулярным, так и правильным регулярным, делает грамматику регулярным и типом 3

Answer 1

Ваша грамматика содержит только правила формы $ a \ до $ , для $ a \ in n $ и $ a \ in t $ .Следовательно, $ l (g)={\ sigma \ in t: s \ \ sigma \ in p \} $ .Вы берете это отсюда.