ТФЯ - 2. Основные положения (продолжение).

yaroslavz аватар

Если отображение одного алфавита в другой удовлетворяет условию h ( x * y ) = h ( x ) * ( y ) для всех слов x из первого алфавита и y из второго, то отображение h называется гомоморфизмом (морфизмом).

Каждый гомоморфизм однозначно определяется своими значениями на однобуквенных словах.

h(L) - язык, который получился в результате гомоморфизма из L.

h^-1(L) - язык, из которого был гомоморфизм.

Порождающей грамматикой называется совокупность двух порождающих алфавитов, правил подстановки (по которым один символ переходит в другой), и начального символа. Из порождающих алфавитов первый - терминальный алфавит (элементы называются терминалами), а второй - вспомогательный алфавит (элементы называются переменными).
Например (e - пустой алфавит),
терминальное множество N = {S}
вспомогательный алфавит A = {a,b,c}
подстановки P = {S -> acSbcS, cS->e}.

Вся эта хуйня - N,A,P и S - является порождающей грамматикой.

Обычно символы терминального алфавита обозначают большими буквами, а вспомогательного - маленькими, чтобы было понятно, где какие.При этом правила порождающей грамматики записывают в таком порядке, что левая часть первого правила есть начальный символ S.
Для обозначения n правил с одинаковыми левыми частями часто используют сокращенную запись a->b1 |...|bn.

Здесь мы имеем универсальное определение грамматики, которое подходит для любого языка, включая нечеловеческие.

Пусть дана грамматика G. Пишем f=>(G)p, (G в математической нотации внизу), если f=hai, p=hbi и a->b in P для некоторых слов a,b,h,i в алфавите N + A. Если f=>(G)p, то говорят, что слово f непосредственно выводимо из слова p.

Если есть цепочка таких выводимых слов, то не стоящие непосредственно рядом слова являются выводимыми. Последовательность при этом называется выводом, а число слов в ней длиной или количеством шагов этого вывода.

Когда из контекста ясно, о какой грамматике идет речь, вместо =>(G) можно писать просто =>

Понятно, что грамматика при этом порождает некоторый язык.

Две грамматики эквивалентны, если они порождают один и тот же язык.

Контекстной грамматикой (контекстно-зависимой грамматикой, грамматикой непосредственно составляющих, НС-грамматикой, грамматикой типа 1, context-sensitive grammar, phrase-structure grammar) называется порождающая грамматика, каждое правило которой имеет вид eAt -> eat.

Контекстно-свободной грамматикой (бесконтекстной грамматикой, КС-грамматикой, грамматикой типа 2, context-free grammar) называется порождающая грамматика, каждое правило которой имеет вид A ->a.

Линейной грамматикой (linear grammar) называется порождающая грамматика, каждое правило которой имеет вид A -> u или A -> u B v.

Праволинейной грамматикой (рациональной грамматикой, грамматикой типа 3, right-linear grammar) называется порождающая грамматика, каждое правило которой имеет вид A->u или A -> u B

Правила вида a -> eps называются эпсилон-правилами. (eps - пустой алфавит).

Каждая праволинейная грамматика является линейной. Каждая линейная грамматика является контекстно-свободной. Каждая контекстно-свободная грамматика без \varepsilon-правил является контекстной грамматикой.

Язык называется языком типа 0 (контекстным языком, контекстно-свободным языком, линейным языком, праволинейным языком), если он порождается некоторой грамматикой типа 0 (соответственно контекстной грамматикой, контекстно-свободной грамматикой, линейной грамматикой, праволинейной грамматикой). Контекстно-свободные языки называются также алгебра.

Классы грамматик типа 0, 1, 2 и 3 образуют иерархию Хомского (Chomsky hierarchy).