КС-языки и их связь с МП-автоматами

Магазинная память (МП)

Язык вида {0ⁿ 1ⁿ /n=1,2,…} не является автоматным, а является контекстно-свободным (КС) языком. Каждый автоматный язык можно распознать конечным автоматом, который допускает цепочки этого языка, т.е. любому автоматному языку соответствует конечный автомат.

Покажем, что приведённому КС-языку не соответствует ни один конечный автомат. Предположим противное. Пусть у К-автомата m состояний. Если m<n, то для запоминания первых n нулей в цепочке потребуется n состояний, что больше числа состояний автомата.

Любая КС грамматика имеет правила вида где . У укорачивающей КС-грамматики допустимо, чтобы .

Опишем укорачивающую КС-грамматику (УКС):

1) S→aAbS

2) S→b

3) A→SAc

4) A→ε

Примеры некоторых выводов:

1. S b

2. S aAbS aSAcbS aScbS abcbS abcbb

S *aScbS S *abcbb

Дерево вывода.

Продемонстрируем, как оно строится:

S

a A b S

S A c

ε

слева направо aScbS

Дерево вывода отражает построение цепочки. Во многих трансляторах языков программирования используют древовидное построение цепочки, и дерево строится либо снизу вверх, либо сверху вниз. В дереве порядок подстановки скрыт, поэтому может быть много выводов, соответствующих одному и тому же дереву. Однако, если на каждом шаге при выводе заменять самый левый нетерминал (или правый в зависимости от договорённости), то получается так называемый канонический вывод. Для каждого дерева существует единственный канонический вывод. Цепочке языка может соответствовать более одного дерева вывода. В этом случае говорят, что грамматика неоднозначна.