Лабораторная работа № 1 по дисциплине «Формальные языки и грамматики»

Тема: «Регулярные языки»

1.      Для заданной грамматики G=(V_N, V_T, P, S) построить 4 цепочки, принадлежащие порождаемому этой грамматикой языку L(G). Длина цепочки должна быть не меньше, чем количество символов в алфавите V_N плюс 2.

2.      Для каждой из этих цепочек построить дерево вывода.

3.      К какому классу грамматик по Хомскому относится данная грамматика и почему?

4.      Построить конечный автомат эквивалентный данной грамматике.

5.      Построенный конечный автомат является детерминированным или недетерминированным и почему?

6.      Построить ориентированный  граф для полученного конечного автомата.

7.      Написать общий вид цепочек, принадлежащих порождаемому этой грамматикой языку L(G).

8.      Написать регулярное выражение e, эквивалентное заданной грамматике G и показать, что L(e) = L(G). 

Лабораторная работа № 2 по дисциплине «Формальные языки и грамматики»

Тема: «Конечные автоматы»

 

1.      Для заданного в виде графа конечного автомата написать его представление в виде AF=(Q, å, d, q₀, F),  то есть написать, чему равны Q, å, d и  F.

2.      Для заданного конечного автомата построить 5 цепочки, допускаемые этим автоматом. Длина цепочки должна быть не меньше, чем количество состояний во множестве Q плюс 2.

3.      Для каждой построенной цепочки  x написать последовательность конфигураций такую, что (q₀, x) |—  (q_i1, x₁)  |— (q_i2, x₂) |—  …  |— (q_f, e), где q_f Î F.

4.      Является ли данный конечный автомат детерминированным или недетерминированным и почему?

5.      Если  данный конечный автомат является недетерминированным, построить эквивалентный ему конечный детерминированный автомат и построить его представление в виде графа.

6.      Написать общий вид цепочек, допускаемых данным конечным автоматом.

7.      Придумать цепочку над алфавитом å, по виду которой можно сказать, что она не подходит под общий вид цепочек, допускаемых данным конечным автоматом и, следовательно, не допускается  данным конечным автоматом. Попытайтесь для этой цепочки написать последовательность конфигураций (q₀, x) |—  (q_i1, x₁)  |— (q_i2, x₂) |—  …  |— (q_f, e), где q_f Î F, чтобы убедиться, что автомат не допускает цепочку.

8.      Для каждой из построенных в пункте 2 цепочки, в соответствии с леммой о разрастании, построить ее представление в виде трех подцепочек x = uvw. Показать, что для построенного разбиения цепочки x выполняются все свойства леммы о разрастании.

9.      Построить регулярную грамматику эквивалентную данному конечному автомату.