Построение НКА иззаданного языка, и последующая переделка НКА в ДКА

Задача вот такая встала.
Из заданного языка {(0+1)*w1w2 | w1 = {0,1,2}* , w2 = {0,1}*}, где * означает, что конструкция может повторяться. Например: 0+10+1000102011001.
Так вот, необходимо выделить определенные правила из языка(регулярного выражения). А потом составить из них Недетерменированный конечный автомат, а потом из этого НКА сделать детерменированный конечный автомат.

Тема известная, но не могу понять как это написать на С#.

0

Сообщение от egor811 Тема известная, но не могу понять как это написать на С#.

А можно увидеть эту известную тему на другом языке программирования?

0

Тема известная по теории. Т.е. в книжках по теории это есть. Принцип понятен, но не понятно куда что записывать в случае C#. Могу начать тему, чтобы разъяснить.

Добавлено через 1 час 40 минут
Ну для начала надо разобрать своим конечным автоматом(уже созданным специально) регулярное выражение, чтобы выделить подвыражения для последующего построения НКА.

0

ок, продолжу.
Для создания регулярных выражений нужно подключить библиотеку регулярных выражений...
Умно, правда?)

Вообще, это делается довольно легко.

1. с помощью обычных string-овых методов удаляешь крайние фигурные скобки (0+1)*w1w2 | w1 = {0,1,2}* , w2 = {0,1}*

2. потом таким же макаром ищешь индекс символа "|" и разбиваешь на две строки (до и после).

3. вторую строку, превращаешь в массив, используя в качестве разделителя ","

4. перебираешь массив (если хочешь - то регулярным выражением) и выделяешь название переменной и ее значения. Результат запихиваешь в какой-нибудь ассоциативный массив. Получится так:
5. если {0,1}* = [01]*, то просто поменяй фигурные скобки на квадратные и удали запятые (если "," тоже может встречаться - то нужно удалять с умом)

6. после этого перебираешь этот массив, ищешь в строке (0+1)*w1w2 все вхождения каждого его поля, и производишь замену на значение.

7. Что значит "переделка НКА в ДКА"? В регулярных выражениях это два разных механизма обработки регулярных выражений (а не их составлений). И какой из них будет использоваться - зависит уже от используемого языка программирования (точней его библиотек РВ). Подробнее читай у Фридла "Регулярные выражения".

1

+1, теперь расскажу зачем мне регулярное выражение прогонять через КА. Да чтобы проверить является ли выражение регулярным, вот зачем, товарищи. Таким образом мы можем проверить является ли это выражение регулярным, выделить алфавит, выделить последовательность правил за один проход для создаваемого НКА, либо послать к черту и сказать, что это нифига не регулярное выражение.

0