Регулярная грамматика

В информатике, регулярная грамматика — формальная грамматика типа 3 по иерархии Хомского. Регулярные грамматики определяют в точности все регулярные языки, и поэтому эквивалентны конечным автоматам и регулярным выражениям. Регулярные грамматики являются подмножеством контекстно-свободных.

Источник: Википедия

Связанные понятия

Контекстно-зависимая грамматика (КЗ-грамматика, контекстная грамматика) — частный случай формальной грамматики (тип 1 по иерархии Хомского), у которой левые и правые части всех продукций могут быть окружены терминальными и нетерминальными символами.

Формальная грамматика или просто грамматика в теории формальных языков — способ описания формального языка, то есть выделения некоторого подмножества из множества всех слов некоторого конечного алфавита. Различают порождающие и распознающие (или аналитические) грамматики — первые задают правила, с помощью которых можно построить любое слово языка, а вторые позволяют по данному слову определить, входит ли оно в язык или нет.

Грамматика сложения деревьев (англ. tree-adjoining grammar, TAG) — это формальная грамматика, придуманная Аравиндом Джоши. Эта грамматика обобщает контекстно-свободную грамматику тем, что элементарной единицей в правилах вывода являются деревья, а не отдельные символы. Таким образом грамматика определяет правила замены узлов дерева на поддеревья (см. дерево в теории графов и дерево в информатике).

Сте́мминг — это процесс нахождения основы слова для заданного исходного слова. Основа слова не обязательно совпадает с морфологическим корнем слова.

Двухуровневая грамматика — это формальная грамматика, которая используется для порождения другой формальной грамматики, например с бесконечным множеством правил. Именно так грамматика ван Вейнгаардена была использована для определения языка Алгол-68. Контекстно-свободная грамматика, которая определяет правила для другой грамматики, может породить в сущности бесконечное множество правил производной грамматики. Это делает двухуровневые грамматики более мощными, чем одноуровневые контекстно-свободные...

Индукция грамматики (или грамматический вывод) — это процесс в машинном обучении для обучения формальной грамматике (обычно в виде набора правил вывода или порождающих правил или, альтернативно, как конечный автомат или автомат другого вида) из набора наблюдений, то есть построение модели, которая описывает наблюдаемые объекты. Более обще, грамматический вывод — это такая ветвь машинного обучения, в которой пространство примеров состоит из дискретных комбинаторных объектов, таких как строки, деревья...

Ле́йпцигские пра́вила глосси́рования (англ. Leipzig glossing rules) — предложенный для унифицированного использования при представлении языковых примеров в лингвистических работах набор правил глоссирования (поморфемной нотации). Включает как собственно правила оформления интерлинеарных глосс, так и список рекомендуемых сокращений (грамматических помет, «ярлыков»), используемых для обозначения грамматических категорий.

Типология порядка слов (в предложении) — один из методов типологической классификации языков, используемых в лингвистической типологии, основанный на понятии базового порядка составляющих: подлежащего (англ. subject), сказуемого (англ. verb) и прямого дополнения (англ. object). Термины «подлежащее» (англ. subject) и «прямое дополнение» (англ. object) в данном случае используются не строго, но для обозначения агентивного и пациентивного участников ситуации. Современное состояние типологии базового...

Грамматика ван Вейнгаардена (также вВ-грамматика или В-грамматика) — это двухуровневая грамматика, которая предоставляет способ определения потенциально бесконечных грамматик через конечное число правил. Формализм был изобретён Адрианом ван Вейнгаарденом для определения некоторых синтаксических ограничений, которые ранее должны были формулироваться на естественных языках, несмотря на свою принципиально синтаксическую сущность. Типичными применениями являются обработка рода и числа в естественных...

Базовый набор слов эсперанто был определён в Первой книге, опубликованной Заменгофом в 1887 году. В ней содержалось около 900 корней, однако, правила языка позволяли говорящим заимствовать слова по мере необходимости. Рекомендовалось заимствовать наиболее интернациональные слова, которые имеют одно основное значение, от которого можно получить другие слова без заимствования многих слов с соответствующими значениями. В 1894 году Заменгоф публикует первый словарь эсперанто «Universala vortaro», который...

Гло́ттохроноло́гия (от др.-греч. γλῶττα «язык» + χρóνος «время» + λόγος «слово; учение») — гипотетический метод сравнительно-исторического языкознания для предположительного определения времени разделения родственных языков, основанный на гипотезе, что скорость изменения базового словаря языка остаётся примерно одинаковой. Эта гипотеза предложена Моррисом Сводешом как попытка аналогии с радиоуглеродным методом измерения возраста органических веществ. В лингвистике предлагается оценивать «лексический...

Расширенная форма Бэкуса — Наура (расширенная Бэкус — Наурова форма (РБНФ)) (англ. Extended Backus–Naur Form (EBNF)) — формальная система определения синтаксиса, в которой одни синтаксические категории последовательно определяются через другие. Используется для описания контекстно-свободных формальных грамматик. Предложена Никлаусом Виртом. Является расширенной переработкой форм Бэкуса — Наура, отличается от БНФ более «ёмкими» конструкциями, позволяющими при той же выразительной способности упростить...

Контекстно-свободная грамматика (КС-грамматика, бесконтекстная грамматика) — частный случай формальной грамматики (тип 2 по иерархии Хомского), у которой левые части всех продукций являются одиночными нетерминалами (объектами, обозначающими какую-либо сущность языка (например: формула, арифметическое выражение, команда) и не имеющими конкретного символьного значения). Смысл термина «контекстно-свободная» заключается в том, что есть возможность применить продукцию к нетерминалу, причём независимо...

Ифку́иль (ифк. Iţkuîl), также Ыфкуил или Илакш — искусственный язык философского направления. Обладает крайней сложностью грамматики и огромным набором фонем, что делает язык весьма трудным для изучения.

Выразительность языка программирования — качество языка, показывающее, насколько разнообразны идеи, которые можно реализовать на этом языке, и насколько легко они читаются.

Интергло́сса (Interglossa) — международный вспомогательный язык, разработанный в 1943 году Ланселотом Хогбеном. Является предшественником языка глоса.

Лексическая типология, или лексико-семантическая типология, — раздел лингвистической типологии, изучающий разнообразие семантики лексических единиц в языках мира.

Афроамериканский английский (чёрный английский, блэк-инглиш) (в англоязычной среде известен под следующими наименованиями: African-American Vernacular English (AAVE), Afro-American English, Black English, American Black English, Black English Vernacular (BEV), Ebonics (англ. ebony и англ. phonics))) — особая разновидность английского языка, объединяющая признаки диалекта и социолекта. Является разговорным, а в некоторых случаях — и литературным языком афроамериканцев.

Кома́нда — это указание компьютерной программе действовать как некий интерпретатор для решения задачи. В более общем случае, команда — это указание некоему интерфейсу командной строки, такому как shell.

Регуля́рные выраже́ния (англ. regular expressions) — формальный язык поиска и осуществления манипуляций с подстроками в тексте, основанный на использовании метасимволов (символов-джокеров, англ. wildcard characters). Для поиска используется строка-образец (англ. pattern, по-русски её часто называют «шаблоном», «маской»), состоящая из символов и метасимволов и задающая правило поиска. Для манипуляций с текстом дополнительно задаётся строка замены, которая также может содержать в себе специальные символы...

Форма Бэкуса — Наура (сокр. БНФ, Бэкуса — Наура форма) — формальная система описания синтаксиса, в которой одни синтаксические категории последовательно определяются через другие категории. БНФ используется для описания контекстно-свободных формальных грамматик. Существует расширенная форма Бэкуса — Наура, отличающаяся лишь более ёмкими конструкциями.

Глагольной группой (ГГ, англ. Verb phrase, VP) в лингвистике называют синтаксическую единицу, состоящую из по меньшей мере одного глагола и его зависимых, таких как дополнения, комплементы и другие модификаторы. Исключение составляет подлежащее, не входящее в состав глагольной группы. Так, в предложении Толстый мужчина быстро положил бриллианты в коробку слова быстро положил бриллианты в коробку могут считаться глагольной группой, состоящей из глагола положил и его зависимых, но не включающей в себя...

Подробнее: Глагольная группа

Связка (ко́пула, лат. copula) в лингвистике — специальное слово для связи подлежащего и сказуемого, выраженного не глаголом, в предложении (в предложениях вроде Петя (—) школьник, Петя был школьником, Дом будет красивым, Курить (—) вредно).

«Аль-кита́б аль-мухтаса́р фи хиса́б аль-дже́бр ва-ль-мука́баля» (араб. الْكِتَاب الْمُخْتَصَر فِي حِسَاب الْجَبْر وَالْمُقَابَلَة‎ — «Краткая книга восполнения и противопоставления») — математический трактат Мухаммеда ибн Мусы аль-Хорезми (IX век), от названия которого произошёл термин алгебра. Также благодаря этой книге появился термин алгоритм.

В теории формальных языков задачей о наименьшей грамматике называется задача нахождения наименьшей контекстно-свободной грамматики, которая порождает уникальную последовательность символов. Размер грамматики частью авторов определяется числом символов в правой части правил вывода.

Подробнее: Задача о наименьшей грамматике

РЕФАЛ (РЕкурсивных Функций АЛгоритмический) — один из старейших функциональных языков программирования, ориентированный на символьные вычисления: обработку символьных строк (например, алгебраические выкладки); перевод с одного языка (искусственного или естественного) на другой; решение проблем, связанных с искусственным интеллектом. Соединяет в себе математическую простоту с практической направленностью на написание больших и сложных программ.

Теория принципов и параметров — этап развития генеративной грамматики, при котором грамматика различных языков описывается с помощью системы универсальных правил, а языковые различия задаются с помощью определённого набора параметров.

В теоретической информатике, точнее, в теории формальных языков, высота итерации — это мера структурной сложности регулярных выражений — высота итерации регулярного выражения равна максимальной глубине вложенности звёздочек, присутствующих в регулярном выражении.

Подробнее: Высота итерации языка

Нисходящий синтаксический анализ (англ. top-down parsing) — это один из методов определения принадлежности входной строки к некоторому формальному языку, описанному LL(k) контекстно-свободной грамматикой. Это класс алгоритмов грамматического анализа, где правила формальной грамматики раскрываются, начиная со стартового символа, до получения требуемой последовательности токенов.

Комплетив — аспектуальное значение глагола, обозначающее достижение финала предельного процесса. В работе Bybee et al. комплетиву дается следующее определение: «сделать что-то основательно, вплоть до завершения».

Адмирати́вность — лингвистическая категория, выражающая удивление говорящего от факта, внезапно установленного им непосредственно перед моментом речи («эпистемическая неожиданность»); в этом случае полученное знание контрастирует с предыдущим состоянием незнания. Это значение рассматривается в качестве особой категории (адмирати́в или мирати́в) либо в рамках категории эвиденциальности.

В информатике неоднозначной грамматикой называется формальная грамматика, которая может породить некоторую строку более чем одним способом (то есть для строки есть более одного дерева разбора). Язык называется существенно неоднозначным, если он может быть порождён только неоднозначными грамматиками.

Подробнее: Неоднозначная грамматика

Еги́петский язы́к — ныне мёртвый язык жителей Древнего Египта. Отдельная ветвь афразийской языковой семьи, в рамках которой, по мнению одних учёных, наиболее близок к семитским, а по мнению других — в частности, И. М. Дьяконова, — к чадским языкам.

Валли́йский язы́к, также уэльский язык или кимрский язык; самоназвание: Cymraeg (произношение: ) или y Gymraeg (произношение: ) — в отличие от уэльского английского (варианта английского языка, сформировавшегося в Уэльсе), относится к бриттской группе кельтских языков; распространён в западной части Британии — Уэльсе (валл. Cymru), а также Чубуте — колонии валлийцев-иммигрантов в регионе Патагонии в Аргентине. Самый распространённый ныне кельтский язык.

Гомоикони́чность (гомоиконность, англ. homoiconicity, англ. homoiconic, от греч. ὁμός — равный, одинаковый + ср.-греч. εἰκόνα — «о́браз», «изображение») — свойство некоторых языков программирования, в которых структура программы похожа на его синтаксис, и поэтому внутреннее представление программы можно определить прочитав текстовую разметку. Если язык гомоиконичен, это означает, что текст программы имеет такую же структуру, как её абстрактное синтаксическое дерево (то есть AST и синтаксис являются...

Вре́мя — грамматическая категория глагола, выражающая отношение времени описываемой в речи ситуации к моменту произнесения высказывания (то есть к моменту речи или отрезку времени, который в языке обозначается словом «сейчас»), который принимается за точку отсчета (абсолютное время) или отношение времени к другой относительной временной точке отсчета (относительное время).

Гиперкорре́ктность, гиперкорре́кция — в языкознании: использование языковых правил за пределами границ их применимости, приводящее к появлению ошибок; гиперкорректность — следствие языковой неуверенности в попытке говорить «правильно», используя более престижные формы. Гиперкоррекции могут подвергаться как написание, так и произношения слова, а также другие аспекты языка.

Амслен появился в начале XIX века в Американской школе для глухих, расположенной в Хартфорде, основанной Томасом Гэллодетом в 1817. В ней использовались педагогические методики Парижского института глухих детей, включая использование французского жестового языка. Так как в школу поступали дети, знавшие другие жестовые языки, в ситуации языкового контакта появился американский жестовый язык.

Пи́сьменность — знаковая система, предназначенная для формализации, фиксации и передачи тех или иных данных (речевой информации и других элементов смысла безотносительно к их языковой форме) на расстоянии и придания этим данным вневременного характера. Письменность — одна из форм существования человеческого языка.

Языком Дика (англ. Dyck language) над 2n буквами называется контекстно-свободный язык над алфавитом...

История математических обозначений — история разработки символов, используемых для компактной записи математических уравнений и формул.

Русский жестовый язык (РЖЯ) — национальная лингвистическая система, обладающая собственной лексикой и грамматикой, используемая для общения глухих и слабослышащих, живущих в России, а также на территории СНГ (Украина, Белоруссия, Казахстан). Грамматика русского жестового языка сильно отличается от грамматики русского словесного языка: поскольку слова сложнее преобразовывать морфологически, то грамматика (например, порядок и образование слов) более строгая, чем в русском языке. Вероятно, принадлежит...

Гло́са (англ. Glosa) — проект международного вспомогательного языка, разработанный в 1972—1992 годах Рональдом Кларком (Ronald Clark) и Уэнди Эшби (Wendy Ashby). Основан на языке интерглосса — проекте искусственного языка, созданном во время второй мировой войны Ланселотом Хогбеном, который опубликовал проект своего языка в 1943 году.

Матричная грамматика — это формальная грамматика, в которой правила вывода группируются в конечные последовательности. Правила вывода не могут применяться по отдельности, а только в последовательности. При применении такой последовательности, замена производится в соответствии с каждым правилом в последовательности, с первой по последнюю. Последовательности называют матрицами.

Ли́нгва де плане́та (также лидепла́, ЛдП; Lingwa de planeta, lidepla, LdP) — искусственный язык, относящийся к категории плановых и апостериорных. Процесс создания был начат в 2006 году в Санкт-Петербурге группой энтузиастов под руководством Дмитрия Иванова, а базовая версия была опубликована в 2010 году. В основу языка были положены наиболее влиятельные на начало XXI века языки планеты: английский, арабский, китайский, немецкий, русский, французский, хинди и т. д.

История арифметики охватывает период от возникновения счёта до формального определения чисел и арифметических операций над ними с помощью системы аксиом. Арифметика — наука о числах, их свойствах и отношениях — является одной из основных математических наук. Она тесно связана с алгеброй и теорией чисел.

Льезо́н, свя́зывание (фр. liaison «связь, соединение») — разновидность внешнего сандхи (изменение звуков на границе слов в предложении) во французском языке. Связывание заключается в появлении непроизносимой согласной буквы на конце слова, когда следующее слово начинается с гласной буквы. К примеру, при добавлении к артиклю множественного числа les (читается ~) слова «дети» фр. enfants (~), между ними появляется звук : . Связывание происходит не всегда: в правилах французского языка есть случаи обязательного...

Частотный анализ, частотный криптоанализ — один из методов криптоанализа, основывающийся на предположении о существовании нетривиального статистического распределения отдельных символов и их последовательностей как в открытом тексте, так и в шифротексте, которое, с точностью до замены символов, будет сохраняться в процессе шифрования и дешифрования.

Сериальная глагольная конструкция, также глагольная сериализация — синтаксическая конструкция, в которой представлена последовательность из двух или более глаголов, функционирующих как единый предикат и описывающих единое событие. Глаголы в сериальной конструкции не связаны друг с другом каким-либо показателем сочинительной или подчинительной синтаксической связи, имеют тождественное грамматическое оформление и являются лексически полноценными. Сериальные глагольные конструкции распространены в креольских...

а б в г д е ё ж з и й к л м н о п р с т у ф х ц ч ш щ э ю я