Как показать, что L = L (G)?

22

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

Мы часто можем спорить на высоком уровне, почему грамматика является адекватным представлением желаемого языка, опуская формальное доказательство. Но что, если мы сомневаемся или по каким-то причинам нам нужны официальные доказательства? Какие методы мы можем применить?

Это должно стать справочным вопросом . Поэтому, пожалуйста, позаботьтесь о том, чтобы дать общие, дидактически представленные ответы, которые иллюстрируются хотя бы одним примером, но, тем не менее, охватывают многие ситуации. Благодарность!

Рафаэль
источник

Ответы:

21

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

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

Пусть формальная грамматика с нетерминалами Н , клеммы Т , правила б и начала символа S N . Обозначим через ϑ ( G ) множество предложений, которые можно вывести из S при заданном δ , то есть α ϑ ( G )G=(N,T,δ,S)NTδSNϑ(G)Sδ . Язык, порожденный G, имеет вид L ( G ) = ϑ ( G ) T . Предположим, мы хотим показать, что L = L ( G ) для некоторого L T .αϑ(G)SαGL(G)=ϑ(G)TL=L(G)LT

Анзац

Вот как мы это делаем. Определим так, чтобыM1,,Mk(NT)

  1. иϑ(G)=i=1kMi
  2. .Ti=1kMi=L

Хотя 2. обычно ясно по определению , 1. требует серьезной работы. Два элемента вместе, очевидно, подразумевают L ( G ) = L по желанию.MiL(G)=L

Для простоты обозначений обозначим .Mзнак равноязнак равно1КMя

Каменистая дорога

Есть два основных шага к выполнению такого доказательства.

  • Как найти (хорошо) ? Mя
    Одна стратегия состоит в том, чтобы исследовать фазы, через которые работает грамматика. Не каждая грамматика поддается этой идее; в общем, это творческий шаг. Это помогает, если мы можем определить грамматику самостоятельно; Имея некоторый опыт, мы сможем определить грамматику, более подходящую для этого подхода.

  • Как доказать 1.?
    Как и при любом заданном равенстве, есть два направления.

    • : (структурная) индукция над производствами G .θ(грамм)Mграмм
    • : Обычно одна индукция М я , начиная с того, который содержит S .Mθ(грамм)MяS

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

пример

Рассмотреть язык

Lзнак равно{aNбNсм|N,мN}

и грамматика с δ, заданным какG=({S,A},{a,b,c},δ,S)δ

SScAAaAbε

для которого мы хотим показать, что . На каких этапах работает эта грамматика? Ну, сначала он генерирует c m, а затем a n b n . Это немедленно сообщает наш выбор M i , а именноL=L(G)cmanbnMi

M0={ScmmN},M1={anAbncmm,nN},M2={anbncmm,nN}.

Поскольку и M 0T = M 1T = , пункт 2. уже учтен. В отношении 1. мы разделили доказательство на две части, как было объявлено.M2=LM0T=M1T=

ϑ(G)M

Проводит структурную индукцию вдоль правил .G

IA: Так как мы успешно закрепляемся.S=Sc0M0

IH: Пусть для некоторого множества предложений , что мы знаем , X M .Xϑ(G)XM

IS: пусть произвольно. Мы должны показать , что в какой бы форме α имеет и то , что правило применяется следующий, мы не оставляем М . Мы делаем это путем полного разграничения регистра. По предположению индукции мы знаем, что (точно) применим один из следующих случаев:αXϑ(G)MαM

  • , то есть ш = S с т в течение некоторого т N . Можно применить два правила, каждое из которых выводит предложение в M : wM0w=ScmmN
    M
    • иScmScm+1M0
    • .ScmAcm=a0Ab0cmM1
  • , т.е. w = a n A bwM1 для некоторого m , n N : w=anAbncmm,nN
    • иwan+1Abn+1cmM1
    • .wanbncmM2
  • : поскольку w T , дальнейшие дифференцирования невозможны.wM3wT

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

ϑ(G)M

Мы выполняем одно (простое) доказательство на . Обратите внимание, как мы объединяем доказательства, чтобы «позже» M i можно было привязать, используя «ранее» M i .MiMiMi

  • : Мы проводим индукцию более м , якорь в S с 0 = S ипомощью S S C на стадии.M1mSc0=SSSc
  • : Зафиксируем m к произвольному значению и индуцируем по n . Зафиксируем в A c m , используя это S S c m A c m в соответствии с первым доказательством. Шаг продвигается через A a A b .M2mnAcmSScmAcmAaAb
  • : Для произвольного m , n N мы используем первое доказательство для S a n A b n c m a n b n c m .M3m,nNSanAbncmanbncm

This concludes the second direction of the proof of 1., and we are done.

We can see that we heavily exploit that the grammar is linear. For non-linear grammars, we need Mi with more than one variable parameter (in the proof(s)), which can become ugly. If we have control over the grammar, this teaches us to keep it simple. Consider as deterring example this grammar which is equivalent to G:

SaAbCεAaAbεCcCε

Exercise

Give a grammar for

L={bkal(bc)manbok,l,m,n,oN,ko,2l=n,m2}

and prove its correctness.

If you have trouble, a grammar:

Consider G=({S,Br,Bl,A,C},{a,b,c},δ,S) with productions

SbSbBlBrBlbBlbABrBrbAbAaAaaCCbcCbcbc

and Mi:

M0={biSbiiN}M1={biBlbooN,io}M2={bkBrbikN,ik}M3={bkaiAa2ibok,o,iN,ko}M4={bkal(bc)iCa2lbok,o,l,iN,ko}M5=L

What about non-linear grammars?

The characterising feature of the class of context-free languages is the Dyck language: essentially, every context-free language can be expressed as the intersection of a Dyck language and a regular language. Unfortunately, the Dyck language is not linear, that is we can give no grammar that is inherently suited to this approach.

We can, of course, still define Mi and do the proof, but it's bound to be more arduous with nested inductions and what not. There is one general way I know of that can help to some extent. We change the ansatz to showing that we generate at least all required words, and that we generate the right amount of words (per length). Formally, we show that

  1. ϑ(G)L and
  2. |L(G)Tn|=|LTn| for all nN.

This way, we can restrict ourselves to the "easy" direction from the original ansatz and exploit structure in the language, ignoring overcomplicated features the grammar may have. Of course, there is no free lunch: we get the all new task of counting the words G generates for each nN. Lucky for us, this is often tractable; see here and here for details¹. You can find some examples in my bachelor thesis.

For ambiguous and non-context-free grammars, I'm afraid we are back to ansatz one and thinking caps.


  1. When using that particular method for counting, we get as a bonus that the grammar is unambiguous. In turn, this also means that the technique has to fail for ambiguous grammars as we can never prove 2.
Raphael
источник