Вопросы по теме 'regular-language'
Каковы теоретические последствия неограниченного просмотра назад?
Большинство языков допускают просмотр назад с фиксированной или конечной длиной. Заметным исключением является .NET, который позволяет использовать оператор *.
Однако регулярные выражения .NET уже могут распознавать сбалансированные круглые скобки...
173 просмотров
schedule
06.09.2022
Разве современные диалекты регулярных выражений не являются регулярными?
Я видел здесь несколько комментариев, в которых упоминается, что современные регулярные выражения выходят за рамки того, что может быть представлено на обычном языке. Как это так?
Какие особенности современных регулярных выражений не являются...
638 просмотров
schedule
23.03.2022
Существует ли алгоритм для определения того, является ли набор всех допустимых экземпляров XML в отношении конкретной схемы XSD обычным языком или нет?
По сути, я хочу знать, можно ли заменить конкретную схему XSD регулярным выражением или нет. Я знаю, что язык XML-схемы может создавать XSD, набор допустимых экземпляров XML которых может относиться к любому типу языка (даже контекстно-зависимому)....
124 просмотров
schedule
08.04.2023
Эквивалентности регулярных выражений
Верна ли следующая эквивалентность регулярного выражения? Почему или почему нет?
(ab)* u (aba)* = (ab u aba)*
* = звезда Клини
u=Союз (Теория множеств)
460 просмотров
schedule
18.11.2022
Является ли язык L = {s ∈ (0 + 1)* | d(s) mod 5 =2 и d(s) mod 7 !=4 } обычный?
При чтении книги у меня возникло это сомнение.
В нем упоминается, что
L = {s ∈ (0+1)* | n0(s) mod 7 = n1(s) mod5 =0} является регулярным, где n0(s) = количество нулей в s и n1(s) = количество 1 в s
Далее упоминается, что
L = {s ∈ (0 + 1)*...
972 просмотров
schedule
22.08.2022
Обычный язык (да или нет)
Мне дали задание проверить, является ли этот язык регулярным:
L = {w∈{a,b,c}* | where the number of a is less than the number of b+c.}
Я не могу найти для этого ни регулярного выражения, ни детерминированного (или нет) конечного автомата. С...
419 просмотров
schedule
01.12.2022
Можем ли мы использовать DFA для синтаксического анализа обычного языка, указанного контекстно-свободной грамматикой, и создания дерева синтаксического анализа?
Как мы знаем, DFA можно использовать для проверки строк на обычном языке.
Пример 1. L=ac(b)*bcb|ad(b)*bb. Строка «acbbbbcb» может быть проверена DFA как правильная.
Кроме того, иногда обычный язык может быть выражен с помощью CFG.
Пример 2....
891 просмотров
schedule
25.02.2024
Можно ли узнать, какие входные символы соответствуют какой части регулярного выражения?
Я пытаюсь создать инструмент, который использует что-то вроде регулярных выражений для поиска шаблонов в строке (не в текстовой строке, но сейчас это не важно). Я знаком с теорией автоматов, т.е. знаю, как реализовать базовое сопоставление регулярных...
535 просмотров
schedule
12.05.2023
Доказательство регулярных языков
Я должен доказать, что это утверждение ложно. Если L1 = {аб| a∈L2, b∉L2} — регулярный язык, то L2 — регулярный язык.
(a и b — строки.) (Предположим, что L1 и L2 имеют одинаковые алфавиты.)
Моя работа: Вопрос можно переписать так: если L2...
272 просмотров
schedule
19.03.2023
Есть ли способ отменить регулярное выражение?
Дано регулярное выражение R , описывающее обычный язык (без причудливых обратных ссылок). Существует ли алгоритмический способ создания регулярного выражения R* , описывающего язык всех слов, кроме тех, которые описываются R ? Это должно быть...
1574 просмотров
schedule
29.03.2023
Может ли кто-нибудь помочь мне с этим доказательством, используя лемму о накачке?
Я только начал читать о лемме о накачке и знаю, как провести несколько доказательств, в основном от противного. Это только этот конкретный вопрос, на который я, кажется, не нахожу ответа. Я понятия не имею, с чего начать. Я могу предположить, что...
1961 просмотров
schedule
25.02.2022
Покажите, что следующий набор над {a,b} является регулярным
Учитывая алфавит {a, b} , мы определяем N a (w) как количество вхождений a в слово w и аналогично для N b (w) . Покажите, что следующий набор над {a, b} регулярен.
A = {xy | N a (x) = N b (y)}
Мне трудно понять, с чего начать...
689 просмотров
schedule
05.12.2022
Математика: предоставление регулярного выражения для языка:
Я продолжаю изучать регулярные выражения и языки. Я прорабатывал несколько вопросов о том, как дать регулярное выражение для представления определенного языка. Вопрос, на котором я немного застрял, звучит так:
Придумайте регулярное выражение,...
164 просмотров
schedule
11.01.2023
Конечность регулярного языка
Все мы знаем, что (a + b)* — это обычный язык, содержащий только символы a и b . Но (a + b)* — это строка бесконечной длины, и она регулярна, поскольку мы можем построить конечные автоматы, поэтому она должна быть конечной.
Кто-нибудь может...
3032 просмотров
schedule
17.12.2022
Как сопоставить все ссылки в регулярном выражении Python?
Я пытаюсь создать регулярное выражение, которое соответствует ссылке из источника страницы. У меня есть текст, отформатированный следующим образом:
что-то здесь вот ссылка
<a class="_5syj"...
247 просмотров
schedule
17.11.2022
Создайте регулярное выражение для определения обычного языка
Язык представляет собой бесконечное множество цепочек, которые определяются следующими условиями.
Условия:
1) The language chains may consist of symbols from the set {1,a,b}.
2) The language chains always start from subchain '1a'.
3) Every...
78 просмотров
schedule
27.11.2022
Существует ли обычный язык, который не является контекстно-свободным языком?
Как следует из названия, не могли бы вы, ребята, объяснить, есть ли какие-либо обычные языки, которые не являются CFG (контекстно-свободный язык)?
48 просмотров
schedule
14.07.2022
обычная/свободная от контекста грамматика
Я надеюсь, что кто-то может помочь мне понять вопрос, который у меня есть, это не домашнее задание, это просто пример вопроса, который я пытаюсь решить. Проблема состоит в том, чтобы определить грамматику, которая генерирует все суммы любого числа...
191 просмотров
schedule
28.11.2023
Как доказать, что это регулярные языки
Итак, у меня есть эти вопросы, по которым мне нужна помощь. Я должен доказать, что это обычные языки. Я понятия не имею, что такое DSQ или DF в вопросе 3 и 4. У меня есть книга «Intro to Comp Theory by Spiser», но я не нашел ничего, что упоминало бы...
211 просмотров
schedule
04.01.2023
Как показать при следующих условиях, что язык L не является контекстно-свободным?
Если у нас есть язык
Теперь я должен использовать язык K, который не является контекстно-свободным, и лемму о том, что пересечение контекстно-свободного языка с обычным языком является контекстно-свободным, чтобы показать, что язык
не...
100 просмотров
schedule
04.06.2022
