为什么是s> ^和A->一种 ？在上下文无关文法中 [英] Why s--> ^ and A --> a ? in Context Free Grammars

问题描述

我一直在阅读：创建上下文无关语法的提示 出于学习目的而发布，我几乎理解了这个概念，但是我不太理解以下内容。

I've been reading: "Tips for creating Context free grammar" post for learning purposes and I nearly understand the concept, but I don't quite understand the following.

如果我们有：

L = {a ^m b ⁿ | m> = n}。

L = {a^m bⁿ | m >= n}.

我了解这一点：

S --> B
B --> aBb
A  --> aA

但是我不明白的是将这些特定值加到最后的概念，例如：

But what I don't understand is the concept of adding to the end of these particular values, such as:

S --> B | ^
B --> aBb | A
A  --> aA | a

为什么要添加 ^ （空）， A 和 a 到这些行的末尾？他们做什么，为什么我们需要他们？

Why do we add ^ (null), A, and a to the end of these lines? What do they do and why do we need them?

非常感谢所有帮助。

推荐答案

您需要他们能够构造语言为 L 的字符串。

You need them to be able to construct the strings that are in the language L.

B- > aBb | A 表示如果您有非终结符 B ，则可以用 aBb 或 A 。 （大写字母表示非结尾，小写字母表示结尾）。

B --> aBb | A means that if you have a nonterminal B it can be replaced by either aBb or A. (Capital letters represent nonterminals and the lower case letters represent terminals).

让我们看一下语法：

S --> B | ^
B --> aBb | A
A  --> aA | a

为什么我们有 | ^ ？您需要它能够生成空字符串。空字符串显然是语言 L 的一部分，因为它包含等量的 a s和 b s。

Why do we have a | ^? You need it to be able to generate the empty string. The empty string is clearly part of the language L since it contain an equal amount of as and bs.

我们为什么有 | A ？能够对 A 使用规则。现在，您可以将 B 替换为 A ，以便您可以插入 aA 或 a 。您需要此规则才能生成具有比 b s更多的 a s字符串。

Why do we have | A? To be able to use the rule for A. Now you can replace B with A so you can insert either aA or a. You need this rule to be able to generate strings that have more as than bs.

我们为什么有 | a ？能够将 A 替换为 a 无需添加需要替换的新非终端。

Why do we have | a? To be able to replace A with a without adding a new nonterminal that need to be replaced.

当我查看此语法时，我会说您需要更改 A-> aA | a 到 A-> aA |一个| ^ 能够生成等量 a s和 b s的字符串。 （因此，您可以将 A 替换为空字符串（或null），而不必添加额外的 a ）

When I look at this grammar I would say that you need to change A --> aA | a to A --> aA | a | ^ to be able to generate strings with an equal amount of as and bs. (So you can replace A with the empty string (or null) instead of having to add an extra a)

假设您要生成字符串 aaabb ：

S       //You start with S
B       //Rule: S --> B
aBb     //Rule: B --> aBb
aaBbb   //Rule: B --> aBb
aaAbb   //Rule: B --> A
aaabb   //Rule: A --> a

这篇关于为什么是s> ^和A->一种 ？在上下文无关文法中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！