自动机理论
研究抽象自动机的理论。抽象自动机是能够识别语言的一种抽象装置。把一串符号输入自动机，如果该符号串是语言中的一个合格的句子，自动机就接收它，反之，就拒绝接收。按照自动机对于语言的识别能力的不同，可将它们分为有限自动机、后进先出自动机、线性有界自动机和图灵机(turing machine)等四种。它们与四种形式文法之间形成整齐的对应关系，即能用图灵机来识别的语言，就能用*0型文法来生成，能用线性有界自动机来识别的语言，就能用*1型文法来生成，余类推。反之亦然。这是语言的生成过程和识别过程的内在联系的反映。 |