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


#1

В теме опубликованы задания к курсовой работе. Варианты заданий определяются по номеру студента в списке группы. Процедура выбора варианта и указания по оформлению находятся в файле заданий на последней странице.

Шаблон LaTex для оформления курсовой появится в этой теме позже.


#2

Сдача первой части курсовой работы будет проходить 6 ноября.

В первой части должны быть выполнены следующие следующие пункты заданий: 1.1 - 1.5, 2.1 - 2.2, 3.1 - 3.4.

Курсовую работу можно оформлять в LaTex (шаблон).


#3

В пятницу состоится контрольная работа.

Список теоретических вопросов и темы практических заданий.


#4

Итоговые баллы за семестр

В пятницу состоится добор баллов. Прошу обязательно присутствовать тех, кому хочется на экзамен, но сумма баллов не позволяет.


#5

В пятницу может состояться пересдача по курсам Основы программирования и Языки программирования.

Прошу старосту совместно с заинтересованными студентами (Рустам Серебряков и Тигран Манукян) определить удобное время пересдачи. Можно за час до начала пары по автоматам, можно после пары, если это возможно. О выбранном времени прошу оставить сообщение на форуме.


#6

В пятницу прошу всех принести с собой тексты курсовых работ. Я их должна буду подписать. Только после этого оценка будет выставлена в ведомость.


#7

Добрый день!

Рустам Серебряков и Тигран Манукян готовы пересдавать экзамены за 2 часа до пары в пятницу.


#8

Добрый вечер! Можно ли получить список теоретических вопросов к первой контрольной? Если он был конечно. А то саму работу я пропустил.


#9

Контрольная точка №1

Теоретические вопросы.

Темы заданий:

По заданному словесному описанию языка построить грамматику,
порождающую этот язык. 

По заданной ПЛ-грамматике найти регулярное выражение,
соответствующее порождаемому этой грамматикой языку. 

По заданной ПЛ-грамматике построить НКА (E-НКА) и провести редукцию
этого автомата к ДКА. 

По КА вычислить регулярное выражение методом исключения состояний.

#10

Спасибо! Со списком понятнее , чего у меня в лекциях не хватает.


#11

Те, кто не успел сдать курсовые работы в семестре, могут сдать работы после нового года с 10 по 15 января. Работы приносите на кафедру АДМ или в а. 320 (кладите в большой комнате возле принтера).


#12

Программа экзамена


#13

Последние баллы за семестр Повышение количества баллов будет проходить на консультациях.


#14

В дни консультаций будет проходить добор баллов. Начало консультаций в 17:00.


#15

Консультация переносится со вторника на среду на 18:30.


#16

вопрос по заданию. у меня 8й вариант для первого задания. у меня w может быть любой длины? тоесть w = 1 , w = 01 , 10 , 11 и тд ? сама граматика:

  • S->0A | 1B | 1
  • A->0C | 1B | 1
  • B->1B | 0N | 0A | 0 | 1
  • C->1B| 1
  • N-> 0

#17

8-й вариант для первого задания чего? В чем суть задания?

Если в принципе, то грамматика задает язык, т.е. множество цепочек над некоторым алфавитом. Длины цепочек, их вид, структура закладываются правилами грамматики. В общем случае длина произвольна. Но можно подобрать грамматику так, чтобы по ее правилам все цепочки были меньше или больше какой-то длины.

В Вашей грамматике длина цепочек не ограничивается.


#18

8й вариант задания для курсовой. язык над 0 и 1 где не более двух нулей подряд и на одной из последних 3х позиций обязательно стоит единица. я старался сделать грамматику под любую длину слов , таких как 01 и таких как 1 (один символ). А судя по вашему ответу я могу сделать грамматику для цепочек длины >3 и только для таких?


#19

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


#20

Спасибо, не знал этого. Но а грамматика которую я составил, она уже находится в нормальной форме Хомского? если верить конспектам, то да. Но у меня не получается однозначно определить рег. выражение. Поэтому спрашиваю про форму, тк не знаю в чем ещё может быть дело. После применения формулы x = ax + b -> x = a*b у меня получается почти на каждой строке уже готовое выражение без нетерминалов. На парах все постепенно подставлялось в другие строки и в конце получалось рег выражение. Одно. а тут…