一元减法的无上下文语法建议？ [英] Context-Free Grammar suggestions for unary subtraction?
问题描述
L = {1 i -1 j = 1 ij ：ij> = 0，i，j > = 0}
L = {1i - 1j = 1i-j: i-j >= 0, i,j>=0}
我对如何构造一个语法来追踪字符串元素的减法感到困惑。我不知道如何开始，并尝试使用表格的等效结构
I'm confused about how to construct a grammar that tracks subtraction of a string element. I have no clue on how to get started on this and attempted to work with an equivaent construction of the form
L = {1 i = 1 ij + 1 j }
L = {1i = 1i-j + 1j}
任何提示或建议。
推荐答案
这里有个提示：总是尝试从括号平衡的角度考虑上下文无关的语言。
Here's a tip: always try to think of context-free languages in terms of parenthetic balancing.
请考虑以下两种语言：
ab ()
aabb (())
aaabbb ((()))
aaaabbbb (((())))
... ...
我们大多数人将第一语言视为重复（某些a后跟b的相同数字 ），第二个为嵌套。但是这两种语言的上下文无关文法是相同的：
Most of us "see" the first language as a repetition (some a's followed by the same number of b's) and the second one as a nesting. But the context-free grammars for these two languages are identical:
S: ab S: ()
| a S b | ( S )
由于CFG正在使用堆栈自动机进行解析，因此嵌套是自然的。第一语言实际上是一定数量的a，然后是相同数量的b，即相反。当然，在您绘制派生树之前，某些b的数量和某些b的倒数看起来是相同的。
Because the CFG is being parsed with a stack automaton, the nesting is natural. The first language is actually some number of a's followed by the same number of b's, reversed. Of course, some number of b's and some number of b's reversed look identical... until you draw the derivation tree.
所以请考虑一元加法语言： $ c> {1 i + j = 1 i + 1 j } 。
So consider the unary addition language: { 1i+j = 1i + 1j }.
很明显，它与 {1 j + i = 1 i + 1 j } （切换加法顺序没有区别）。或者，将加法写成简单的串联： {1 j 1 i = 1 i + 1 j } 。现在，我们可以将对称性进行分组：（这里的括号是用于显示分组的元符号，而不是语言的一部分）： {1 j （ （ 1 i = 1 i ） + ） 1 j } 。
Clearly that's the same as { 1j+i = 1i + 1j } (switching the order of addition makes no difference). Or, writing out the addition as a simple concatenation: { 1j 1i = 1i + 1j }. Now, we can just group the symmetry: (here the parentheses are metasymbols to show grouping, not part of the language): { 1j ( ( 1i = 1i ) + ) 1j }.
哪个会导致
L1 → =
L1 → 1 L1 1
L2 → L1 +
L2 → 1 L2 1在CFG中，添加的内容有些模糊，但是清楚发生了什么：我们允许在 = 的两边带有相同的1的句子，并且只有一个 + 插入到右侧的任何位置。 （通过对语法进行非常简单的更改，我们可以允许多个 + 号，使语法接受具有多个加数的加法方程。）
In the CFG, the addition has been obscured a bit, but it's clear what is happening: we're allowing a sentence with the same number of 1s on both sides of an =, with a single + being inserted anywhere on the right-hand side. (With a very simple change to the grammar, we could allow multiple + signs, making out grammar accept addition equations with more than one addend.)
这篇关于一元减法的无上下文语法建议？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
