Упражнения

В ниже перечисленных упражнениях требуется построить конечный автомат, распознающий язык L. Алфавит S={a,b,c}.

1. αÎL тогда и только тогда, когда в слове α встречается не более трех букв а подряд.

2. αÎL тогда и только тогда, когда в слове α сочетание ab встречается не более двух раз.

3. αÎL тогда и только тогда, когда в слове α содержится подслово bbсс.

4. αÎL тогда и только тогда, когда слово α имеет длину не более 8 и содержит одинаковое число букв a и b.

5. αÎL тогда и только тогда, когда слово α содержит четное число букв.

6. αÎL тогда и только тогда, когда слово α содержит нечетное число букв а.

7. αÎL тогда и только тогда, когда при наличии в слове α буквы a там встречается также и буква b.

8. αÎL тогда и только тогда, когда каждая буква алфавита встречается в слове α не более двух раз.

Построение анализаторов КС-языков по порождающим грамматикам.

Синтаксические анализаторы делятся на два класса:

1. Анализаторы, которые, читая входные цепочки, строят их деревья выводов в порождающих грамматиках, как говорят, снизу вверх. Те анализаторы, которые просматривают входные цепочки один раз слева направо или справа налево, являются анализаторами данного класса, к ним относятся и МП-автоматы. Такие анализаторы работают детерминировано, но они построены для однозначных грамматик и имеют ряд других ограничений.

2. Анализаторы, которые строят деревья выводов, начиная с корня и вершин, соответствующим наиболее крупным синтаксическим конструкциям. Говорят, что такие анализаторы работают в режиме сверху вниз. Многие анализаторы этого класса просматривают входные цепочки многократно. Определенным недостатком анализатором является то, что в них процесс недетерминирован, но анализаторы этого класса более универсальны – многие из них не требуют никаких ограничений на КС-грамматики.

Ниже мы рассмотрим три метода автоматического построения анализаторов по КС- и УКС-грамматикам. Анализаторы, получаемые с помощью первых двух методов, работают в режиме снизу вверх и могут быть представлены в виде детерминированных устройств. Анализаторы, которые строятся по третьему методу, представляют собой алгоритмы упорядоченного перебора правил исходных грамматик с целью нахождения деревьев выводов входных цепочек сверху вниз.