Теория автоматов и формальных языков


#21

Грамматика G=(N, Sigma, P, S) находится в нормальной форме Хомского, если каждое правило из P имеет один из следующих видов:

  1. A -> AB, A, B - нетерминалы
  2. A -> a , A - нетерминал, a - терминал
  3. S -> Epsilon, причем, S не должно встречаться в правых частях других правил.

Вы путаете нормальную форму Хомского и составление системы уравнений, решив которую можно получить н.н.т. (для S - н.н.т. представляет собой рег. выражение для L(G))


#22

Скиньте мне фото Ваших вычислений


#23

сейчас не смогу. но через час сделаю


#24


#25

В Вашем решении есть ошибки. Начнем по порядку.

  1. Правило B -> 0N ; N -> 0 можно перевести в B -> 00, а N удалить.

Вы составляете ПЛ-грамматику, а не автоматную, так что это допустимо и облегчит дальнейшие вычисления.

  1. Решение системы основывается на систематическом применении следующего:

если X = AX + B , уравнение, где X - неизвестное, а A,B - регулярные выражения над некоторым алфавитом, то X = A*B

Таким образом у Вас уже в уравнении для S ошибка.

S = 0A + 1B + 1

S - неизвестное, так что вся правая часть - это B , а Вы пытаетесь записать решение относительно A

Вам надо подставить в уравнение для B решения для остальных неизвестных, когда оно будет зависеть только от B, то можно будет записать решение в виде A*B . Дальше все получится.


#26

#27

Да, начинает быть похоже на правду :slight_smile:


#28

В пятницу 12 февраля в 16:00 пройдёт экзамен по теории автоматов и формальных языков. Сбор возле а. 320. Приглашаются все, у кого есть допуск.


#29

а это можно упрощать? или в таком виде и осталять? а то автомат какой то не очень получается)


#30

Дальше можно построить автомат по грамматике и преобразовывать его. А что понимать под упрощением? Чем сейчас автомат сложен?


#31

нуу…он мне не нравится. По-другому не могу объяснить)


#32

27 февраля в 16:00 в а. 305 будет проходить экзамен по теории автоматов. Приглашаются все желающие и подготовленные.


#33

Экзамен будет проведён в пятницу 1 апреля с 15:30. Сбор возле а. 320


#34

Пересдача экзамена будет проводиться в субботу 2 апреля с 12:00. Сбор возле а. 320

В пятницу 1 апреля экзамен можно тоже сдавать.


#35

Экзамен будет проведён в пятницу 8 апреля с 15:30. Сбор возле а. 320


#36

Экзамен переносится на 15 апреля. Время и место те же. Всем приятной подготовки! Следующий добор в четверг 14 апреля.


#37

Здравствуйте. А скажите как вас можно найти ? А то по расписанию не нашёл. По поводу курсовой - показать её.А то надо бы уже сдать…


#38

Пятница с 14:00 (нижняя неделя) Четверг с 15:20 до 15:40 А. 204 или 320


#39

Не нашёл(


#40

Здравствуйте, скажите сегодня вы будете на факультете? курсовую показать