Описание тега chomsky-normal-form
In formal language theory, a context-free grammar is said to be in Chomsky normal form if all of its production rules are of the form:
A -> BC or
A -> α or
S -> ε
where A, B and C are nonterminal symbols, α is a terminal symbol (a symbol that represents a constant value), S is the start symbol, and ε is the empty string.
1
ответ
Удаление нулевых произведений из контекстно-свободной грамматики
X -> zZ|yW|WW Y->Z Z->X|ε W->Y|X Буду ли я прав, полагая, что в качестве Y только Z в качестве своего терминала ε переходит к Y, давая: X -> zZ|yW|WW Y->Z|ε Z->X W->Y|X затем? X -> zZ|yW|WW|z Y->Z Z->X W->Y|X
12 дек '14 в 13:17
3
ответа
Преобразование грамматики в нормальную форму Хомского?
Переведите приведенную ниже грамматику в нормальную форму Хомского. Дайте все промежуточные шаги. S -> AB | aB A -> aab|lambda B -> bbA Итак, первое, что я сделал, это добавил новую переменную запуска S0 так что теперь у меня есть S0 -> …
19 сен '11 в 00:14
0
ответов
Хромская нормальная форма производства единицы
У меня есть следующее, что мне нужно конвертировать в CNF: S -> Aux NP VP S -> VP VP -> Verb NP VP -> VP PP Verb -> book Aux -> does То, что я до сих пор это: S -> X1 VP X1 -> Aux NP S -> Verb NP S -> VP PP VP -> Ver…
15 дек '17 в 03:52
1
ответ
Хомская нормальная форма правильности
У меня есть эти постановки: S->aSb S-> eps (eps=empty string) Я должен применить нормальную форму Хомского Мои рассуждения: 1) устранить правила eps учитывая: S->aSb S-> eps Я получил: S->ab S->aSb 2) устранить единичные правила Не…
06 июл '11 в 07:35
1
ответ
Производные для контекстно-свободной грамматики
В конечном итоге я хочу преобразовать следующий CFG в нормальную форму Хомского: S→aSbS∣bSaS∣ε Однако я не уверен, правильно ли я делаю деривации - вот что у меня есть: Замена нетерминалов с терминалами S→aabb S→ε Может кто-нибудь сказать мне, если …
05 окт '14 в 20:50
1
ответ
Как вы делаете последний шаг при конвертации CFG в CNF?
Дано: S->AcA|BcB A->ccBc|ABA|cc B->c step1 S0->S S->AcA|BcB A->ccBc|ABA|cc B->c step2 // change symbol to terminals? S0->S S->ABA|BBB A->BBBB|ABA|BB B->c step3 // split? S0->S S->ABA S->BBB A->BBBB A->…
13 мар '15 в 19:34
2
ответа
Алгоритм преобразования нормальных форм Хомского
Почему мы добавляем новое начальное состояние S0 -> S, когда хотим преобразовать грамматику в нормальную форму Хомского? Что пойдет не так, если мы этого не сделаем? Сначала я думал, что это из-за правил эпсилон. Но мы не удаляем эпсилон-правило из …
31 май '16 в 22:57
2
ответа
Преобразование в нормальную форму Хомского
Мне нужна твоя помощь У меня есть эти постановки: 1) A--> aAb 2) A--> bAa 3) A--> ε Я должен применить нормальную форму Хомского (CNF). Чтобы применить вышеупомянутое правило, я должен: устранить ε производства ликвидировать унитарные произ…
26 июн '11 в 14:30
1
ответ
Всегда ли конкатенация нерегулярного языка с обычным языком не является регулярной?
Я хотел бы знать, если конкатенация между двумя языками (один обычный, а другой нет) всегда не является регулярной, или может случиться так, что вывод является обычным языком. Благодарю.
21 ноя '16 в 13:46
0
ответов
Преобразование CFG в форму Хомского Normal
Используя лемму прокачки для обычных языков, покажите, что язык L = {ai, bj ck | i, j, k - неотрицательные целые числа, и i=j или i=k } не регулярно Дизайн CFG для языка выше Это то, что я придумал Answer: G = (V,,R, S) with set of variables V = {S,…
15 окт '14 в 05:17
1
ответ
Контекстная грамматика для КЛЛ
enter code hereПривет, это мой вопрос Дайте контекстно-свободную грамматику для КЛЛL = {a^nb^mc^n | m, n ∈ N0} Мой ответ S-> ASC| B A-> aA| a B-> bB| b C-> cC| c Будь мой ответ или нет? Я не уверен в этом. Нужна помощь. заранее спасибо
20 июн '17 в 16:44
1
ответ
Какой будет форма CNF этой вероятностной грамматики?
Если PCFG, как, NP -> ADJ N [0.6] NP -> N [0.4] N -> cat [0.2] N -> dog [0.8] Какой будет форма CNF? Это будет следующим? NP -> ADJ NP [0.6] NP -> cat [0.08] NP -> dog [0.32] или что-то еще?
29 сен '16 в 11:32
1
ответ
Как я могу доказать, что дифференцирование в нормальной форме Хомского требует 2n - 1 шагов?
Я пытаюсь доказать следующее: Если G является контекстно-свободной грамматикой в нормальной форме Хомского, то для любой строки w принадлежит L(G) длины n ≥ 1, для любого вывода w требуется ровно 2n-1 шагов. Как мне доказать это?
12 июл '12 в 16:07
1
ответ
Закрытие Клини в нормальной форме Хомского
Пусть n будет любым терминалом. Рассмотрим следующее, предположительно правильное, представление клинской звезды над n: N → n N | ε (где ε - пустой терминал.) Википедия говорит: Каждая грамматика в нормальной форме Хомского не зависит от контекста, …
11 сен '14 в 14:59
0
ответов
CYK построить дерево разбора из таблицы
Как построить дерево синтаксического анализа после получения таблицы CYK? Я не понял, что пытается сказать Википедия.Пример: A - C A - B B,D C,F E B,D Как мне вернуть список правил, применяемых для перехода от A к BCED (или любой другой комбинации б…
25 ноя '16 в 18:23
3
ответа
Нормальная форма Хомского - теория вычислений
Я хочу изменить грамматику на нормальную форму Хомского (CNF). Это пример S--> AB | ɛ A--> aASb | a B--> bS Я пытаюсь решить это S --> [A] [B] [A] --> [aA] [Sb] | [a] [aA] --> [a] A [Sb] --> s [b] [a] --> a [b] --> b Я не …
13 дек '10 в 17:23
4
ответа
Нормальная хомская форма
Почему мы переводим грамматику в нормальную форму хомского? Есть ли преимущество?
03 фев '11 в 08:19
1
ответ
Полиномиальный размер CFG такой, что каждый терминал в слове встречается четное число раз (большой алфавит)
Найдите контекстно-свободную грамматику (CFG) для языка L всех слов так, чтобы каждый терминал в слове встречался четное число раз по возможно большому алфавиту Σ Мой длинный подход (единственный нетерминал это S): S ⟶ ε | SS x ∈ Σ: S ⟶ xSx x, y ∈ Σ…
13 дек '10 в 14:00
0
ответов
Алгоритм добавления списка после сравнения символа со строкой
Добавление нескольких строк в список на основе некоторых элементов этой строки В списке такой строки ['ASA', 'A', 'Ab', 'Ad', 'c'] Как я могу добавить несколько строк и стать этим списком ['ASA', 'A', 'Ab', 'Ad', 'c', 'SA', 'AS', 'S', 'e', 'b', 'd']…
08 фев '19 в 10:28
2
ответа
Является ли этот результат синтаксического анализатора CYK правильным?
Я пытаюсь изучить алгоритм разбора CYK. Для этого набора правил грамматики правильны ли получающиеся таблицы для двух данных предложений? S -> NP VP VP -> VB NP NP -> DT NN PP -> IN NP NP -> NP PP NP -> NN VP -> VP PP IN -> w…
22 май '12 в 10:32