对下列文法进行化简,删除其中的无用符号、空产生式以及单一产生式。 S→aABC|bCES|aE A→bE|SCD|d B→dFS|aBC C→aES|bE D→aAC|d E→aCE|aCT|ε F→eATB|aF T→eT|eF
时间: 2023-12-26 22:06:39 浏览: 159
经过化简后的文法如下:
```
S → aABC | bCES | aE
A → bE | SCD | d
B → dFS | aBC
C → aES | bE
D → aAC | d
E → aCE | aCT
F → eATB | aF
T → eT | eF
```
其中,我们删除了无用符号和空产生式,并将单一产生式进行了合并。下面是具体的步骤:
1. 删除无用符号
我们可以通过以下步骤删除无用符号:
- 找到所有能够推导出终结符号的非终结符号,这些非终结符号是有用的。
- 找到所有能够推导出有用符号的符号,这些符号也是有用的。
- 删除所有没有被找到的非终结符号和产生式。
根据上述步骤,我们可以得到以下有用符号:
```
S, A, B, C, D, E, F, T
```
然后我们可以找到所有能够推导出有用符号的符号:
```
S → aABC | bCES | aE
A → bE | SCD | d
B → dFS | aBC
C → aES | bE
D → aAC | d
E → aCE | aCT | ε
F → eATB | aF
T → eT | eF
```
因此,我们可以删除以下无用符号和产生式:
```
删除无用符号:ε
删除产生式:E → ε
```
2. 删除空产生式
我们可以通过以下步骤删除空产生式:
- 找到所有可以推导出空符号的非终结符号。
- 对于每个非终结符号,找到所有包含该非终结符号的产生式。
- 对于每个包含该非终结符号的产生式,将其拆分成两个产生式,一个包含该非终结符号,一个不包含该非终结符号。
根据上述步骤,我们可以得到以下可以推导出空符号的非终结符号:
```
E
```
然后我们可以找到所有包含该非终结符号的产生式:
```
E → aCE | aCT | ε
```
因此,我们可以将其拆分成以下产生式:
```
E → aCE | aCT
C → aES | bE | ε
```
3. 删除单一产生式
我们可以通过以下步骤删除单一产生式:
- 对于每个非终结符号,找到所有只能推导出一个符号串的产生式。
- 对于每个这样的产生式,将其删除,并将该非终结符号在其他产生式中的出现替换为该产生式右侧的符号串。
根据上述步骤,我们可以找到以下单一产生式:
```
C → aES
```
因此,我们可以将其删除,并将该非终结符号在其他产生式中的出现替换为该产生式右侧的符号串:
```
C → aEAS | bE
```
最终,我们得到了经过化简后的文法:
```
S → aABC | bCES | aE
A → bE | SCD | d
B → dFS | aBC
C → aEAS | bE
D → aAC | d
E → aCE | aCT
F → eATB | aF
T → eT | eF
```
阅读全文
相关推荐

















