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