Поиск ЦКА

Создайте DFA таким образом, что нижний индекс L 4 = {0,1}* - {0,01}* и перечислите первые пять строк в лексикографическом порядке.

У меня возникли проблемы с выводом того, что подразумевает подстрочный индекс L 4, это язык строк с длиной 4? Кроме того, когда мы вычитаем два языка, можем ли мы выбрать строку «1», вычитаемую из пустой строки, то есть можно выбрать первую {0,1}* длиной 1, вычитаемую из {0,01}* длины 0. ?


dfa regular-language
person azureskys    schedule 06.04.2014    source источник
comment
Обычно это просто означает язык с индексом имени L 4.   -  person Bergi    schedule 07.04.2014
comment
Вы не можете вычитать строки. Может ли это означать, что вы должны вычесть один язык из другого: L_4 = L({0,1}*) - L({0,01}*)?   -  person Bergi    schedule 07.04.2014
comment
Вы правы, Берги, я имел в виду язык {0,1}*, но под строкой я подразумеваю строку, которую создает язык.   -  person azureskys    schedule 07.04.2014
comment
Я думаю, что ваш вопрос не имеет никакого смысла (больше). Не могли бы вы перефразировать часть о выборе строки? Вычитание языков работает так же, как установка разности: все строки из L1, которых нет в L2.   -  person Bergi    schedule 07.04.2014
comment
Я думаю, что моя проблема заключается в вычитании двух языков. Например, найдем ли мы все строки длины один в обоих языках, а затем создадим новый язык L4, такой, что каждая строка в L4 содержит строку в {0,1}*, но не в {0,01}*? И сделайте это итеративно для строки длины 2 3... Таким образом, первые пять строк L4 будут 1 10 11 011 101   -  person azureskys    schedule 07.04.2014
comment
Нет, не каждая строка в L4 содержит строку… но каждая строка в L4 является строкой…. Ваши первые пять строк выглядят нормально. Однако обратите внимание, что вы не должны создавать язык, а просто DFA. И помните, что означает дополнение   -  person Bergi    schedule 07.04.2014
comment
Каким именно будет DFA? Я сделал один, но не знаю, как воспроизвести его в stackoverflow. Я не думаю, что это правильно после прочтения части дополнения. Будет ли это просто DFA для L ({0,1} *), а затем взять его дополнение?   -  person azureskys    schedule 07.04.2014
comment
Извините, я имею в виду DFA для {0,01}*, что означает, что есть только два состояния?   -  person azureskys    schedule 07.04.2014
comment
@azureskys изучает дополнение dfa L = {0, 1}* - {0, 01}* означает дополнение языка {0, 01}*   -  person Grijesh Chauhan    schedule 07.04.2014
comment
Да, это было бы просто дополнением DFA для этого языка {0,01}*, но есть более двух состояний (не забудьте состояние ошибки)   -  person Bergi    schedule 07.04.2014

Ответы (2)


arrow_upward
0
arrow_downward

Язык {0,01}* — это набор строк, в которых перед каждой 1 должен стоять один 0. Например, в этом языке есть 00010001, а 10000 или 0001111 — нет. {0,1}*, с другой стороны, это все строки с алфавитом {0,1}. Теперь, вычитая эти результаты, получается язык, в котором по крайней мере одна единица и все единицы предшествуют любому 0. Например, 1111000 находится в L_4, а 000000 или 011111 — нет.

person Community    schedule 26.10.2016

arrow_upward
0
arrow_downward

Обозначение {0, 1}* — {0, 01}* установлено вычитанием — это означает «язык всех строк в {0, 1}*, которых нет в {0, 01}*». Когда они пишут

L4 = {0, 1}* - {0, 01}*

Я считаю, что они определяют новый язык под названием L4, который равен приведенному выше выражению.

Чтобы решить эту проблему, вам может быть полезно заметить, что L4 является дополнением языка {0, 01}*. Один из способов решить эту проблему — построить DFA для {0, 01} *, а затем поменять местами все состояния принятия и отклонения. Это даст вам DFA для L4.

Остальную часть проблемы я оставлю читателю в качестве упражнения. :-)

person templatetypedef    schedule 26.10.2016