Определение грамматики CFG

Question

Определите CFG (контекстно-свободный язык), который генерирует язык:

L = {a ^ nb ^ mc ^ n |n, m> = 0}

Может кто-нибудь сказать мне, как решить проблему?

Насколько я понимаю, L состоит из таких элементов, как: {aabbbcc} (я предположил, что n = 2и m = 3)

спасибо заранее Иоахим

Answer 1

Это звучит как домашнее задание, поэтому я просто дам несколько советов.

Как вы могли бы сделать количество совпадений a и c в производстве контекстной грамматики?

Какую продукцию вы могли бы использовать для генерации последовательности b?

Как эти две подзадачи можно объединить в одну контекстно-свободную грамматику?

Answer 2

Рассмотрим контекстную грамматику, которая генерирует язык

L1 = {a^nc^n : n >= 0}

например

G1 = <{S},{a,c},S,{S -> aSc,S-> λ}>

Производные в G1 можно охарактеризовать следующим образом:

G1 =>1 S        (via S)
   =>* a^nSc^n  (via n >= 0 applications of S -> aSc)
   =>1 a^nc^n   (via S -> λ)

Грамматика G1 устанавливает необходимые отношения между числом и размещением a и c на языке L1, а затем завершается применением правила S -> λ.

Рассмотрите, как деривация в G1 завершается, применяя правило S -> λ, и как вы можете сгенерировать последовательность m >= 0 b вместо пустой строки. Вот решение проблемы, которое немного более общее. Предположим, у нас есть язык L2, сгенерированный грамматикой

G2 = <V,N,S2,P>

Чтобы генерировать строки в L2, окруженные равным числом a и c, правила G1 могут быть дополнены следующим образом для получения грамматики G1':

G1' = <{S} ∪ V,{a,c} ∪ N,S,{S -> aSc,S -> S2} ∪ {P}>

Чтобы решить вашу проблему, пусть L2 будет языком {b}* и G2 обычной грамматикой, которая его генерирует.