Философия / логика WikiProject | (Номинальный класс заглушки, Низкая важность) |
---|---|
ВикиПроект по математике | (Номинальный стартовый класс, низкий приоритет) |
---|---|
Лучшее определение
Разве не было бы проще определить язык Дайка как язык, следующий грамматике:
N → [N] | [] N | N [] |
Я думаю, что это гораздо более читабельно, чем обозначение вставки / удаления. 84.58.215.217 19:12, 21 ноября 2006 г. (UTC)
Да, он более читабелен, но не так удобен для формальных доказательств. Тем не менее, здесь его стоит представить.
Еще одно замечание: на самом деле существует более одного языка Дейка, а именно по одному для каждого положительного целого числа, обозначающего количество различных типов скобок. 132.187.9.77 15:43, 2 апреля 2007 г. (UTC)
Ах, и я думаю, что ваша грамматика неверна (например, она не может генерировать [[]] [[]]). Возможно, лучше было бы
S -> SS | [S] | ε
132.187.9.77 15:47, 2 апреля 2007 г. (UTC)
Я думаю, что грамматическая форма более удобочитаема и удобна для использования в учебных целях. Мы сохраним обе формы, чтобы дать таким бедным студентам, как я, более простой способ закрепить эту концепцию в своем сознании.
Краткая и правильная грамматика должна быть следующей:
S → (S) S | ε
Я не согласен с 132.187.9.77, что контекстно-свободная грамматика менее удобна для формальных доказательств. Определение контекстно-свободной грамматики является индуктивным и, таким образом, допускает легкую структурную индукцию. Если бы кто-то формализовал доказательства о языке Дейка, например, в Coq, это было бы проще всего с помощью CFG. 72.70.58.29 ( разговорное ) 18:55, 14 августа 2017 (UTC)
Признание в классе сложности ТК 0
Я удалил следующее:
- Язык Дейка с двумя различными типами круглых скобок можно распознать в классе сложности TC 0 .
Во-первых, не цитируется. Во-вторых, я считаю, что это утверждение неверно. Садборо («О детерминированных контекстно-свободных языках, многоголовых автоматах и возможностях вспомогательного выталкивающего хранилища», STOC '76: Материалы восьмого ежегодного симпозиума ACM по теории вычислений, стр. 141–148, 1976) показал, что Язык Дайка с двумя типами скобок является (в некотором смысле) полным для DCFL (набор всех языков лог-пространства, сводимых к детерминированным контекстно-свободным языкам). Если Dyck_2 разрешимо в TC ^ 0, то все DCFL = TC ^ 0, что неизвестно и действительно маловероятно. —Предыдущий неподписанный комментарий добавлен 129.93.165.5 ( обсуждение ) 18:19, 28 марта 2008 г. (UTC)
ОК. После проверки и повторной проверки оказалось, что исходное утверждение было правильным. Я восстановил его, но он все еще нуждается в цитировании. Следует процитировать Barrington and Corbett, Information Processing Letters 32 (1989) 251-256. —Предыдущий неподписанный комментарий добавлен 129.93.165.5 ( обсуждение ) 20:53, 31 марта 2008 г. (UTC)
Добавляю ссылку на вышеупомянутую статью dvberkel ( talk ) 05:52, 5 августа 2015 (UTC)
уточнение функций вставки и удаления
Я не понимаю функций вставки и удаления. Во-первых , мне кажется, что мне нужно знать, находится ли первый символ строки в нулевой или первой позиции. Позиция один более естественна, но, очевидно, поскольку области определения функций включают ноль, читатель должен сделать вывод из этого, что строки начинаются с позиции ноль. Было бы полезно сделать это явным или изменить определения на первый символ в позиции один. Во-вторых , в то время как для функции вставки я могу декодировать почти слишком короткое «вставленное в j-ю позицию» в «вставленное перед круглой скобкой в позиции j» (два символа не помещаются в одну позицию.), Я не могу декодировать функцию удаления "'[]', удаленную с j-й позиции". Позиция j содержит только одну круглую скобку, что означает удаление пары из этой позиции? Я склонен интерпретировать это как «Удалите круглую скобку в позиции j, а затем найдите соответствующую круглую скобку, которая может быть на много позиций слева или справа, и удалите ее тоже». Но эта интерпретация не соответствует граничному условию «delete (u, j) не определено, если j> | u | - 2». «2» должно быть «1». Есть комментарии, прежде чем я войду и начну возиться с текстом статьи? ИОЛ Джефф ( разговор ) 21:40, 10 октября 2009 г. (UTC)
круглые скобки () по сравнению с квадратными скобками []
Скобки круглые. В статье следует либо продолжать использовать квадратные скобки и называть их «квадратные скобки», либо перейти на круглые скобки и продолжать называть их «круглыми скобками». Я предпочитаю скобки, но не решаюсь редактировать в этом направлении, если в литературе обычно используются квадратные скобки. ИОЛ Джефф ( разговор ) 21:50, 10 октября 2009 г. (UTC)
Я изменяю использование «круглых скобок» на «скобки», но после введения я уберу слово «квадрат». dvberkel ( разговор ) 05:43, 5 августа 2015 (UTC)
Отсутствуют языки Дейка с более чем одним типом круглых скобок
В этой статье отсутствует большая часть теории языков Дайка. Хороший источник: http://planetmath.org/encyclopedia/WellBalanced.html Кроме того, упомянутая теорема Хомского-Шютценбергера неверна (см. Обсуждение этой статьи). Кроме того, Хомский-Шютценбергер относится к языкам Дика с n типами скобок для некоторого n , а не обязательно n = 2 . - Предыдущий неподписанный комментарий добавлен 201.231.234.10 ( обсуждение ) 06:53, 8 сентября 2011 г. (UTC)
Лучшее определение для n ≥ 1
Данное определение с использованием дисбаланса является точным только для языка Дейка с использованием одной пары скобок. Если дисбаланс - это просто разница между количеством противоположных скобок, тогда вы должны рассмотреть быть словом Дайка, поскольку общий дисбаланс положительный и положительный для каждого префикса слова (и для каждого типа скобок).
Я считаю, что простое и вполне понятное определение - это класс эквивалентности через транзитивное замыкание отношения такой, что для каждого символа и каждое слово .
Я думаю, что грамматика, генерирующая язык Дейка, довольно проста и тоже помогает пониманию: поскольку это указывает на то, что каждое слово Дика получается путем объединения двух слов Дика или заключения одного в противоположные скобки. - Предшествующий неподписанный комментарий, добавленный Mak4wiki ( обсуждение • вклад ) 12:43, 3 октября 2016 г. (UTC)
Действительно трудно читать с квадратными скобками.
Можно ли обсудить переход на скобки из текущих квадратных скобок? Приведенные различные примеры строк в некоторых шрифтах выглядят как непонятные вертикальные линии и прямоугольники. 72.70.58.29 ( разговорное ) 18:10, 14 августа 2017 (UTC)
- Я полностью согласен. Выбор символа является произвольным, и использование круглых скобок существенно улучшит читаемость. 148.88.169.37 ( разговорное ) 13:29, 22 января 2018 (UTC)