Описание тега kleene-star
В теории вычислений звездочка клини (*) является регулярной операцией, относительно которой закрыты все регулярные языки.
1
ответ
Звёздная семантика Клини и сравнение множеств
Скажем, у нас есть два языка L1 и L2. Следующее условие считается ложным? (L1L2)* = L1*L2* Я предполагаю это, потому что говорю: Левая сторона условия: L1 = {a,b} L2 = {c,d} C = L1.L2 C = {ac,ad,bc,bd} C* = {empty, 'acad','adbc','bdac',...} Правая с…
06 окт '18 в 22:58
1
ответ
Если регулярный язык содержит только звезду Клини, то возможно ли, что это происходит от объединения двух нерегулярных языков?
Я хочу знать, что при заданном обычном языке L, который содержит только оператор звезды Клини (например, (ab)*), возможно ли, что L можно сгенерировать путем конкатенации двух нерегулярных языков? Я пытаюсь доказать, что L может быть сгенерирован то…
07 апр '12 в 15:20
1
ответ
Почему нельзя создать конструкцию замыкания Клини для NFA?
Большинство источников, таких как http://www.cs.may.ie/staff/jpower/Courses/Previous/parsing/node5.html, предполагают, что замыкание Клини должно быть построено с 4 узлами. Почему это не может быть построено только с 2, как показано ниже?
01 янв '17 в 15:15
3
ответа
Регулярное выражение: имеет ли звезда Клини дистрибутивное свойство?
Будет ли разница между (aa)* а также (a*a*)? Есть ли распределительная собственность?
07 мар '13 в 07:13
4
ответа
Если язык L не является регулярным, является ли L* регулярным?
Имеет смысл предположить, что L* не регулярно. Тем не менее, я не могу найти доказательства того или иного заключения.
15 окт '15 в 05:51
1
ответ
Клини Стар в программировании. Разница между (a|b)* и a*b*?
В чем разница между (a|b)* а также a*b*? Можете ли вы показать больше примеров звезды и моделей Клини? Я искал так много сайтов в Google, но он дал очень мало результатов по этой теме. Я был бы очень благодарен, поскольку я пытаюсь понять, как работ…
02 фев '12 в 03:44
3
ответа
Как оценить это регулярное выражение?
Я просто изучаю регулярные выражения, поэтому я просто хочу убедиться, что мое понимание верно. 01* означает 0, за которыми следуют 0 или более повторений из 1. 1* + 01* означает 0 или более повторений 1 ИЛИ 0, за которыми следуют 0 или более повтор…
01 дек '13 в 09:03
1
ответ
Клини замыкание для бесконечного подмножества
Пусть L = {an | n> = 0}, где а также для всех n >= 1. Таким образом, L состоит из последовательностей любой длины, включая последовательность длины 0. Пусть L2 - любое бесконечное подмножество L. Мне нужно показать, что всегда существует DFA для рас…
18 фев '14 в 13:40
2
ответа
Неоднозначность при переходе: как обработать строку в NFA?
Я сделал DFA из данного регулярного выражения, чтобы соответствовать тестовой строке. Есть несколько случаев, когда .* происходит. (например .*ab) Допустим, сейчас машина находится в состоянии 1. В ДФА, .* относится к переходу для всех символов к се…
25 мар '13 в 14:28
2
ответа
Как использовать оператор Клини-звезды (*) или его вариант (+) с переменными в sparql?
У меня есть некоторый рабочий код для получения всех предков термина в иерархии. Следующий: PREFIX skos: <http://www.w3.org/2004/02/skos/core#> PREFIX skos-xl: <http://www.w3.org/2008/05/skos-xl#> PREFIX rdf: <http://www.w3.org/2000/0…
14 ноя '18 в 01:56
1
ответ
Нужна помощь по рекурсивному определению для двух языков S* и T*, где S={aa,b} и T={w1,w2,w3,w4}
В настоящее время я прохожу курс Теории автоматов, и у меня возникли следующие проблемы. Я пришел к ответу на 1-й вопрос, но смутился из-за постановки 2-го вопроса. (i) Дайте рекурсивное определение для языка S*, где S = {aa,b}. Шаг 1: Lamba, aa, b …
26 авг '15 в 20:30
3
ответа
Мне нужна помощь в поиске всех строк, не включенных в (a*b)*
Я делаю это для домашней работы. Мне нужно написать регулярное выражение для языка над (a, b) который включает в себя все строки, не включенные в язык (a*b)* например 'aaaaaaabaaaaaaaabaaaaaaabaaaabaaaaaaaaab' будет работать. Поэтому я ищу регулярно…
09 дек '13 в 23:24
5
ответов
Бесконечный язык не может быть регулярным? Что такое конечный язык?
Я прочитал это в книге о вычислимости: (Теорема Клини). Язык является регулярным тогда и только тогда, когда его можно получить из конечных языков, применяя объединение трех операций, конкатенацию, повторение конечное число раз. Я борюсь с "конечным…
01 июл '13 в 19:54
1
ответ
Закрытие Клини в нормальной форме Хомского
Пусть n будет любым терминалом. Рассмотрим следующее, предположительно правильное, представление клинской звезды над n: N → n N | ε (где ε - пустой терминал.) Википедия говорит: Каждая грамматика в нормальной форме Хомского не зависит от контекста, …
11 сен '14 в 14:59
0
ответов
Лучший способ реализовать Kleene Star в Java
Как я могу реализовать оператор звезды Клини, чтобы определить замыкание Клини до определенного уровня?
12 мар '17 в 12:36
2
ответа
grep: Когда звезда клини (*) должна совпадать?
Я учусь grep но у меня возникли трудности с пониманием работы метасимвола клины. Страницы руководства описывают, что * соответствует предыдущему символу ноль или более раз. Я использую файл с именем test со следующим содержанием *a 123ab 1234 abcdef…
08 янв '13 в 06:43
1
ответ
Когда клинская звезда конечного языка свободна?
Я ищу ссылки, которые дают алгоритм для решения этой проблемы: Задача: для заданного конечного алфавита Σ и конечного языка L ⊆ Σ* определить, является ли L* свободным моноидом. Эквивалентно, проблема состоит в том, чтобы определить, учитывая конечн…
11 мар '15 в 00:17
1
ответ
Как переписать грамматику без контекста, чтобы она была LR(1)?
Для данной контекстной свободной грамматики: S -> G $ G -> PG | P P -> id : R R -> id R | epsilon Как мне переписать грамматику так, чтобы она была LR(1)? У текущей грамматики есть конфликты сдвига / уменьшения при разборе ввода "id: .id…
06 ноя '14 в 18:28
1
ответ
Контекстная грамматика с хотя бы одной звездой Клини
Я пытаюсь создать контекстно-свободную грамматику, которая генерирует все регулярные выражения над {a,b} хотя бы с одной звездой Клини. Что я сделал до сих пор это: S ::= A + S | A A ::= B . A | B B ::= T | B* | (S) T ::= a | b | eps Я предполагаю, …
15 июн '14 в 10:47
2
ответа
Определение, если два языка равны [Регулярное выражение]
Готовилась к экзамену и переживала эту проблему: Определить, является ли набор строк, представленных R1, подмножеством R2? R1 = (01 +10)* R2 = ((01)* + (10)*) Моя попытка: так как там представлены одинаковые выражения, я попытался доказать, что они …
06 дек '13 в 05:09