Префиксная грамматика
В теоретической информатике и теории формального языка префиксная грамматика — это тип системы переписывания строк , состоящий из набора строк правил переписывания и похожий на формальную грамматику или систему полу-Туэ . Особенностью префиксных грамматик является не форма их правил, а способ их применения: только префиксы переписываются . Префиксные грамматики описывают в точности все регулярные языки . [1]
Формальное определение
[ редактировать ]Префиксная грамматика G представляет собой тройку (Σ, S , P ), где
- Σ — конечный алфавит
- S — конечное множество базовых строк над Σ
- P — конечное множество правил производства вида u → v , где u и v — строки над Σ.
Для строк x , y мы пишем x → G y (и говорим: G может получить y из x за один шаг), если существуют строки u, v, w такие, что и v → w в P. находится Обратите внимание, что → G — бинарное отношение на строках Σ.
Язык G , обозначаемый , — это набор строк, выводимых из S за ноль или более шагов: формально, это набор строк w таких, что для некоторых s в S , s R w , где R — замыкание транзитивное → G .
Пример
[ редактировать ]Префиксная грамматика
- Σ = {0, 1}
- С = {01, 10}
- Р = {0 → 010, 10 → 100}
описывает язык, определенный регулярным выражением
