非回文的上下文无关文法

问题描述

我需要一个CFG来生成回文以外的字符串。已经提供了解决方案，如下所示。（计算理论简介-Sipser）

  R-> XRX | S 
 S-> aTb | bTa 
 T-> XTX | X | < epsilon> 
 X->一个| b 
  

我对这种语法的工作原理有一个大致的了解。它要求通过产生 S->插入一个子串，该子串的任一半上都有相应的不等字母。 aTb | bTa ，从而确保永远不会产生回文。

我将写下前两个产品的语义， ，

• S 生成的字符串不能是回文，因为它们的第一个和最后一个字母是不等于


• R 由至少一个 S 组成字符串，确保它永远不会回文。

我不完全理解第三种产品的语义。 p>

  T-> XTX | X | < epsilon> 
 X->一个| b 
  

我的看法是，T可以生成a和b的任意组合，即{a， b} *。为什么不能像

  T-> XT | < epsilon> 
 X->一个| b 
  

两个不是等效的吗？由于后面的内容更加直观，为什么不使用它呢？

解决方案

我认为这本书的结构显示出某些对称性更好的阅读方式。

后者似乎很直观。但是，如果您想到回文式的定义或构造，您可能会理解为什么用这种方式写作才有意义。

如果您有回文式，您将构造类似此

如果我们想破坏构造，我们只需要确保一层看起来像这样（我用T成为一层，S在T之后的某一步变成S）

因此形成了内层（T）和外层（R）以及违反回文结构（S ）。甚至认为T似乎是多余的，但它形成了与R类似的结构，从而表达了这种结构的意图。

I need a CFG which will generate strings other than palindromes. The solution has been provided and is as below.(Introduction to theory of computation - Sipser)

R -> XRX | S
S -> aTb | bTa
T -> XTX | X | <epsilon>
X -> a | b

I get the general idea of how this grammar works. It mandates the insertion of a sub-string which has corresponding non-equal alphabets on its either half, through the production S -> aTb | bTa, thus ensuring that a palindrome could never be generated.

I will write down the semantics of the first two productions as I have understood it,

• S generates strings which cannot be palindromes because their 1st and last alphabets are not equal
• R consists of at-least one S as a sub-string ensuring that it is never a palindrome.

I don't completely understand the semantics of the third production, i.e. .

   T -> XTX | X | <epsilon>
   X -> a | b

The way I see it, T can generate any combination of a and b, i.e. {a, b}*. Why could it not have been like

T -> XT | <epsilon>
X -> a | b

Aren't the two equivalent? As the later is more intuitive, why isn't it used?

解决方案

The construction the book I believe is shows some symmetry for better reading.

It means it first construct anything, T. Then there is a wrapper S, so that it becomes no longer a palindrome S, and then build everything upon it.

The latter might seems to intuitive. However, if you think of the definition or construction of palindrome, you might understand why writing in such way make sense.

If you have a palindrome, you would construct something like this

And if we want to violate construction, we just need to make sure that there is one layer looks like this (I use T to be one layer and S to something one step after T)

And other layer we generally do not care

So that forms the inner layer (T) and outer layer(R) and the layer that violates the construction of palindrome(S). Even thought T seems to be redundant, but it forms the similar construction like R, thus expressing the intention of the construction.

这篇关于非回文的上下文无关文法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！