Описание тега chomsky-hierarchy
The Chomsky hierarchy is a containment hierarchy of classes of formal grammars.
1
ответ
Распознавать максимальный тип формального языка
В настоящее время я пытаюсь изучать и понимать формальные языки и грамматику. Я понимаю иерархию Хомского, но нашел задачу, в которой я не знаю, как они нашли решение. Задача: G=({S},{a,b},S,P) P={S->epsilon, S->aS, S->Sb} Каков максимальны…
01 фев '17 в 13:54
0
ответов
Возможно ли иметь производство с одним или несколькими терминалами в LHS рекурсивно перечислимого языка?
Поскольку рекурсивно перечислимая грамматика не ограничена, возможно ли иметь производство с одним или несколькими терминалами в LHS (т.е. без нетерминалов)?
18 ноя '17 в 08:56
2
ответа
Что это? Ищете правильную терминологию, что здесь происходит
Рассмотрим следующую грамматику, которая имеет явный недостаток в том, что касается генераторов синтаксического анализатора: "Start Symbol" = <Foo> "Case Sensitive" = True "Character Mapping" = 'Unicode' {A} = {Digit} {B} = [abcdefABCDEF] {C} …
16 май '15 в 17:20
1
ответ
Пример нелинейного, недвусмысленного и недетерминированного КЛЛ?
В классификации формальных языков Хомского мне нужны примеры Non-Linear, Unambiguous and also Non-Deterministic Контекст-Free-Language(N-CFL)? Линейный язык: для которого возможна линейная грамматика ( ⊆ CFG), например L 1 = {a n b n | n ≥ 0} Детерм…
30 окт '12 в 16:10
1
ответ
Контекстно-зависимая грамматика
Я ищу контекстно-зависимую грамматику, которая описывает следующий язык: L = { ww | w ∈ {a,b}*, |w| ≥ 1} <br> У меня есть проблемы с тем фактом, что никакие правила, такие как X -> ε, не допускаются, и поэтому я не могу поместить нетерминал, у…
17 июл '13 в 13:37
2
ответа
Хомская иерархия и LL(*) парсеры
Я хочу разобрать язык программирования. Я много читал о формальных языках и иерархии Хомского и ANTLR. Но я не смог найти информацию о том, как соотнести языки ANTLR v3 как синтаксический анализатор рекурсивного спуска LL(*), принимающий иерархию ch…
14 янв '09 в 08:57
1
ответ
Типы хомского языка
Я пытаюсь понять четыре различных типа языка Хомского, но определения, которые я нашел, на самом деле ничего не значат для меня. Я знаю, что тип 0 - свободная грамматика, тип 1 - контекстно-зависимый, тип 2 - контекстно-свободный, а тип 3 - обычный.…
23 май '12 в 12:01
1
ответ
Пример языка, который не является рекурсивно перечислимым, и его дополнительный язык также не является RE
Только язык, о котором я не могу думать, который не принадлежит классу RE, является диагональным языком, но, к сожалению, его дополнительный язык рекурсивно перечислим. У кого-нибудь есть какие-либо идеи?
23 ноя '13 в 14:43
4
ответа
Рекурсивные языки против контекстно-зависимых языков
В иерархии Хомского множество рекурсивных языков не определено. Я знаю, что рекурсивные языки являются подмножеством рекурсивно перечислимых языков и что все рекурсивные языки разрешимы. Что меня интересует, так это то, как рекурсивные языки сравнив…
16 июн '10 в 21:14
1
ответ
Regexp parse type-3 грамматика
Чтение иерархии Хомского... ... я знаю, что регулярное выражение не может анализировать грамматики типа 2 (контекстно-свободные грамматики), а также типы 1 и тип 0. Могут ли регулярные выражения анализировать / перехватывать ВСЕ грамматики типа 3 ( …
13 фев '12 в 14:11
1
ответ
Почему эта грамматика не зависит от контекста?
Я получил эту грамматику: G = (N, Эпсилон, P, S) с N = {S, A, B} Epsilon = {a}, P: S -> e S -> ABA AB -> aa aA -> aaaA A -> a Почему это грамматика только типа 0? Я думаю, что это из-за aA -> aaaA, но я не вижу, как это противоречи…
15 ноя '15 в 18:18
1
ответ
Регулярная грамматика для моего Regex/DFA
У меня есть следующее регулярное выражение: ((abc)+d)|(ef*g?) Я создал DFA (надеюсь, это правильно), который вы можете увидеть здесь http://www.informatikerboard.de/board/attachment.php?attachmentid=495&sid;=f4a1d32722d755bdacf04614424330d2 Задача с…
14 янв '15 в 17:40
1
ответ
Преобразование спецификации языка в правила производства (не уверен, что это CFG или CSG)
Я должен написать функцию, которая проверяет, являются ли входные строки допустимыми для данной языковой спецификации. Я думал, что это будет стандартная форма CFG -> нормальная форма Хомского, затем синтаксический анализ CYK, но одно из правил в яз…
06 май '12 в 20:36
5
ответов
Существует ли стандартная грамматика C++?
Стандарт определяет официальную грамматику C++? Я искал, но нигде не нашел. Кроме того, я хотел бы прочитать немного о грамматике C++ подробно, например, к какой категории грамматик она относится и т. Д. Любые ссылки, указывающие мне правильное напр…
17 май '10 в 14:21
2
ответа
Возможен ли генератор синтаксического анализа типа 1 Хомского?
Глядя на иерархию грамматик Хомского, я обнаружил, что для грамматик типа 2 (контекстно-свободных грамматик) существуют очень хорошие инструменты, помогающие в создании программного обеспечения для чтения их из текста в пригодную для использования с…
19 июн '18 в 07:03
1
ответ
Является ли лексическая грамматика Rust регулярной, контекстно-свободной или контекстно-зависимой?
Лексическая грамматика большинства языков программирования довольно не выразительна, чтобы быстро ее выучить. Я не уверен, к какой категории относится лексическая грамматика Rust. Большинство из них кажется регулярным, возможно, за исключением необр…
28 апр '17 в 10:09
0
ответов
Как проверить, является ли язык регулярным, контекстно-свободным, дет. без контекста или типа 0
Я должен решить для нескольких языков, являются ли они обычными, контекстно-свободными, дет. без контекста или типа 0. Я понимаю, как показать язык не быть регулярным (используя лемму прокачки), но как очень быстро решить его для других типов языков…
03 мар '15 в 12:48
2
ответа
Какой язык является SQL?
Является ли SQL контекстно-свободным языком или каким-либо другим типом языка?
27 окт '14 в 19:31
1
ответ
Иерархия Хомского - контекстно-зависимые языки типа 1
Я пытаюсь понять иерархию Хомского на разных уровнях. Я проверил несколько примеров, и вот тот, который я действительно не понимаю. Может быть, кто-то знает, почему этот язык не является контекстно-зависимым: S → aA A → aA | ε B → bA
29 мар '16 в 15:39
1
ответ
Конечная и Бесконечная языковая путаница
Недавно я начал изучать теорию формального языка и столкнулся с некоторыми проблемами с конечными и бесконечными языками. Мне сказали, что все конечные языки являются регулярными. Однако, читая записки, данные мне, грамматика с постановками: S -->…
28 апр '15 в 15:16