5 正则文法与有限状态自动机

正则文法,属于3型文法,是最简单的语法形式,仍具有生成力。他们可以描述串联 (连接两个字符串在一起),重复,选择,但却无法表达嵌套。正则文法可能是形式语言学中最好理解的部分,几乎所有有关的问题都能得到解答。