为什么这不是上下文无关的语法? [英] Why is this not context free grammar?

问题描述

我隐约记得{a ^ n b ^ n c ^ n is，n> = 0}不是上下文无关的.

I vaguely recall { a^n b^n c^n is, n>=0 } not context free.

但以下不是捕获上述内容的有效的上下文无关文法

But isn't the following a valid context free grammar that captures the above

S-> abcS S->空

S -> abcS S -> null

引用维基百科:

"在形式语言理论中，上下文无关文法(CFG)是一种形式文法，其中每个生产规则都具有以下形式: V→w 其中V是单个非终端符号，w是终端和/或非终端的字符串(w可以为空)."

"In formal language theory, a context-free grammar (CFG) is a formal grammar in which every production rule is of the form V → w where V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals (w can be empty)."

推荐答案

以防万一您想知道为什么它不是上下文无关的语法，以下是一个简短的解释:

Just in case you are wondering why it's not a context free grammar, here's a quick explanation:

上下文无关文法是可以由下推自动机识别的文法，下推自动机是带有堆栈的有限状态自动机.

A context free grammar is a grammar that can be recognized by a push-down automaton, which is a finite state automaton with the addition of a stack.

CFG的一个示例是a ^ n b ^ n.如果您考虑一下，我们可以为看到的每个"a"将令牌推送到堆栈中，并为看到的每个"b"将令牌弹出堆栈.如果我们在任何时候都会失败 -弹出后推送令牌("b"后跟"a") -完成字符串的处理，但是堆栈上仍然有令牌("a"比"b"更多) -尝试弹出一个空堆栈("b"多于"a")

An example of a CFG is a^n b^n. If you think about it, we can push a token on our stack for every 'a' that we see and pop a token off the stack for every 'b' we see. We will fail at any point if we - push a token after popping (a 'b' followed by an 'a') - finish processing the string but we still have tokens on the stack (more 'a's than 'b's) - try to pop an empty stack (more 'b's than 'a's)

如果您考虑如何使用下推式自动机识别a ^ n b ^ n c ^ n，您可能会发现在经过一些游戏之后这是不可能的.

If you think about how to recognize a^n b^n c^n with a push-down automaton, you will probably realize that is impossible after some playing around.

希望有帮助.

这篇关于为什么这不是上下文无关的语法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！