What does context-free mean in CFLs?

Yao Yao on September 4, 2021

这真的是困扰了我很多年的问题,而且我发现这还不是中文教材的锅,老外的很多教材也是上来就 CFL,也不告诉你这个 context 到底是啥 context,这个 free 是怎么个 free 法。我就纳闷了,多讲这么几句怎么就这么难呢……

这个问题,还是得看 Stack Overflow,金牌答案是:Doval on What does “context-free” mean in the term “context-free grammar”?简单说就是:

It means all of its production rules have a single non-terminal on their left hand side.

比如一个极端的例子:

\[S \rightarrow aa | bb\]

与 CFL 对应的是 context-sensitive language (CSL),它可能存在这样的 production rules:

\[\begin{aligned} aS & \rightarrow aa \newline bS & \rightarrow bb \end{aligned}\]

non-terminal $S$ 可能 derive 出 $a$ 或者 $b$,但是 $S$ 的 derivation 具体要看 $S$ 前面是 terminal $a$ 还是 terminal $b$。这个 $S$ 前面的 terminal 就是 $S$ 的 context。或者我觉得叫 “conditional derivation” 也是好理解的。

P.S. 我就没遇到一本教材有提 CSL 的,这对比一下不是很利于理解么……怎么就这么难呢!

问题下面还有一位 Basile Starynkevitch 的 comment,提到了 Chomsky hierarchy,哪天需要重学 Languages vs Automation 的时候可以参考下。这张表和这个图在教材里竟然看不到我也是不理解……



blog comments powered by Disqus