Самостоятельная работа

Слушателям курса предлагается реализовать некоторые из рассмотренных алгоритмов самостоятельно.

Требования к оформлению заданий

  • Email на victorp@math.spbu.ru
  • "[formlang]" в поле subject (+ задание или тема письма)
  • Тело письма в соответствии с сетикетом: http://www.ietf.org/rfc/rfc1855.txt
  • В аттаче - архив с исходными кодами программ и тестами для задания 
  • В корне архива
    • для Java - build.xml, понимаемый инструментом Apache ant, порождающий в этой же папке запускающийся jar
    • для C# - все .cs файлы. Компляция - csc /out:a.exe *.cs
    • для C/C++ - *.c или *.cpp. Будут компилироваться gcc:  gcc -I. -Wall
  • Тесты для задания 
  • Формат ввода/вывода для каждого задания определен отдельно. Если не указано другое, то: 
    • Входные данные задаются через аргументы командной строки. 
    • Вывод осуществляется на стандартное устройство вывода (консоль)
    • Программа не должна ничего читать из стандартного устройства ввода или с клавиатуры. (Например, не должно быть "Console.ReadLine();")
    • Подсказка по VisualStudio: чтобы в консольном приложении после запуска не закрывалось окно следует программу запускать с помощью Ctrl+F5.

Задания

Важно! В последнем столбце таблицы указаны даты, после которых прием решений производиться не будет.

 Описание  Баллы
 1         Моделирование недетерминированного конечного автомата
Реализовать программу, осуществляющую моделирование недетерминированного конечного автомата.
Формат вызова:
a.exe {файл с описанием НКА{файл входной цепочки}
Формат файла с описанием НКА:
N1 a1 a2 ... aN1 
N2
...
qi aj qk1 qk2 ... qkm
qi & qk1 qk2 ... qkm 
...
N3 qi1 qi2 ... qiN3
где
N1 - количество символов во входном алфавите
a1 a2 ... aN1 - символы входного алфавита (заглавные и строчные латинские буквы, десятичные цифры, знаки препинания, различные скобки)
N2 - количество состояний НКА
qi aj qk1 qk2 ... qkm - запись в управляющей таблице: переход из состояния qi в одно из состояний qk1 qk2 ... qkm по символу a (e-переход: &)
N3 - количество конечных состояний
qi1 qi2 ... qiN3 - перечисление конечных состояний

Формат файла входной цепочки:
{ASCII символы}
Пробелы и прочие невидимые символы игнорируются.
Формат выдачи:
В случае успешного завершения (в скобках множества состояний, соответствующих конфигурациям автомата):
(qi1 ...) ai1 (qi21 qi22...) ai2 ... (qiN1 qiN2 ...) SUCCESS
В случае завершения в неконечном состоянии:
(qi1 ...) ai1 (qi21 qi22...) ai2 ... (qiN1 qiN2 ...) FAIL
В случае обнаружения недопустимого символа:
(qi1 ...) ai1 (qi21 qi22...) ai2 ... () FAIL

Пример: NFA1.7z
допуск
/1
18.10.2012
 2 Проверка эквивалентности ДКА
Реализовать программу, осуществляющую проверку эквивалентности двух ДКА.
Формат вызова:
a.exe {файл с описанием ДКА-1{файл с описанием ДКА-2}
Формат файла с описанием ДКА:
N1 a1 a2 ... aN1 
N2
...
qi aj qk
...
N3 qi1 qi2 ... qiN3
где
N1 - количество символов во входном алфавите
a1 a2 ... aN1 - символы входного алфавита (заглавные и строчные латинские буквы, десятичные цифры, знаки препинания, различные скобки)
N2 - количество состояний ДКА
qi aj qk - запись в управляющей таблице: переход из состояния qi в qk по символу aj
N3 - количество конечных состояний
qi1 qi2 ... qiN3 - перечисление конечных состояний

Формат выдачи:
В случае, если ДКА эквивалентны:
TRUE
В случае, если ДКА не эквивалентны, необходимо также найти строку, на которой они различаются (один принимает, а другой -- нет):
FALSE a1...am
Пример: dfaeq1.7z
 5 ??.11.2012

 3 Построение табличного LL(1) аналлизатора
Реализовать программу, осуществляющую построение табличного LL(1) анализатора (сильного или полного) и моделирование его работы.
Формат вызова:
a.exe {файл с описанием грамматики{файл входной цепочки}
Формат файла с описанием грамматики:
N1 -> a11 a12 ... a1N1 
N2 -> a21 a22 ... a2N2 
...
Nm -> am1 am2 ... amNm 
где
  • Ni - нетерминальные символы (слова, начинающимися с заглавной латинской буквы).
  • N1 - стартовый символ - первый нетерминал в файле.
  • Количество символов в правой части соответствующего правила (N1, N2, ..., Nm) может быть равно 0 (эпсилон-цепочка).
  • Терминальные символы (строчные латинские буквы, десятичные цифры, знаки препинания, математические операторы, различные скобки)
  • aij - нетерминальные или терминальные символы.
Формат файла входной цепочки:
{ASCII символы}
Пробелы и прочие невидимые символы игнорируются. 

Формат выдачи:
В случае успешного завершения левый анализ цепочки (включая терминальные символы):
N1 ai1 ai2 ai3 ... aik SUCCESS
В случае обнаружения ошибки при распозновании, магазин анализа, соответствующий левому анализу максимально-корректного префикса:
N1 ai1 ai2 ai3 ... aik FAIL
В случае невозможности построения однозначного LL(1) анализатора (грамматика не является LL(1)-грамматикой):
FAIL
 допуск -
 4 Преобразование грамматики к НФХ
Реализовать программу, осуществляющую преобразование КС-грамматики к нормальной форме Хомского.
Формат вызова:
a.exe {файл с описанием грамматики}
Формат файла с описанием грамматики:
N1 -> a11 a12 ... a1N1 
N2 -> a21 a22 ... a2N2 
...
Nm -> am1 am2 ... amNm 
где
  • Ni - нетерминальные символы (слова, начинающимися с заглавной латинской буквы).
  • N1 - стартовый символ - первый нетерминал в файле.
  • Количество символов в правой части соответствующего правила (N1, N2, ..., Nm) может быть равно 0 (эпсилон-цепочка).
  • Терминальные символы (строчные латинские буквы, десятичные цифры, знаки препинания, различные скобки)
  • aij - нетерминальные или терминальные символы.
Формат выдачи:
КС-грамматика в НФХ, описывающая тот же язык, либо
FAIL
если грамматику невозможно представить в НФХ. Замечание: если в результате преобразования в НФХ нетерминал описывает тот же язык, то он должен сохранить имя, если язык изменяется, то его следует переименовать.
 3  -
 5 Минимизация ДКА
Реализовать программу, осуществляющую минимизацию ДКА.
Формат вызова:
a.exe {файл с описанием ДКА}
Формат файла с описанием ДКА:
N1 a1 a2 ... aN1 
N2
...
qi aj qk
...
N3 qi1 qi2 ... qiN3
где
N1 - количество символов во входном алфавите
a1 a2 ... aN1 - символы входного алфавита (заглавные и строчные латинские буквы, десятичные цифры, знаки препинания, различные скобки)
N2 - количество состояний ДКА
qi aj qk - запись в управляющей таблице: переход из состояния qi в qk по символу aj
N3 - количество конечных состояний
qi1 qi2 ... qiN3 - перечисление конечных состояний

Формат выдачи:
  ДКА с минимальным количеством состояний эквивалентный исходному. Формат аналогичен 
Пример: dfamin.zip
 4/
допуск
 -


ċ
NFA1.7z
(0k)
Victor Polozov,
4 окт. 2012 г., 2:57
ċ
dfaeq1.7z
(0k)
Victor Polozov,
4 окт. 2012 г., 2:58
ċ
dfamin.zip
(0k)
Victor Polozov,
29 дек. 2012 г., 5:18
ċ
ll1.zip
(1k)
Victor Polozov,
8 нояб. 2012 г., 15:16
ċ
ncf.zip
(0k)
Victor Polozov,
8 нояб. 2012 г., 15:18
Comments