如何将常规语法转换为有限自动机：S->aaB|aB|epsolon， B->bb|bS|aBB

Question

如何处理aaB和ab，在获得aa输入时，我使三个状态包括启动状态。我能再次添加一个从开始状态到状态B的过渡吗?还是我得做点别的?

Answer 1

对于这个问题，我们首先需要了解规则语法

规则语法，又称第三类语法。

规则语法生成规则语言。它们的左手边有一个非末端，右手边有一个单一的末端，或者后面跟着一个非末端。

结果必须是这样的形式:

A ⇢ xB 
A ⇢ x
A ⇢ Bx
where A, B ∈ Variable(V) and x ∈ T*  i.e. string of terminals.

规则语法的类型:

1. 左线性语法(LLG):在LLG中，如果所有结果都是

   的形式，则结果的形式为

   A ⇢ Bx
   A ⇢ x
   where A,B ∈ V and x ∈ T*
   

2. 右线性语法(RLG):在RLG中，如果所有的产品都是

   的形式，则产品的形式为

   A ⇢ xB
   A ⇢ x
   where A,B  ∈ V and x ∈ T*
   

type-3语法生成的语言是一种规则语言，可以为其设计FA。FA也可以转换成type-3语法

给出的语法是Right linear grammar。

正则语法有限自动机图像

由于有两个变量，我们需要创建两个状态。使S为终态