тип 3 грамматика - регулярное выражение

Question

Я прочитал заметку, что у грамматиков типа 3 не может быть обоих этих производств

A-> aB
A-> Ba

, где A, B не являются терминалами, а a является терминалом

Я знаю достаточноо типе 3, но я не могу понять выше

Answer 1

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

A -> '(' B
B -> A ')'
A -> '1'

Если вы предположите, что A является начальным нетерминалом, ваш язык выдаст вам все слова

((...((1))...))

где числоСкобки с обеих сторон одинаковы.Это, однако, не является языком типа 3 (неофициально, правильный счетчик должен считать, поэтому он не может быть конечным состоянием).