【摘要】 本文以终止状态接受定义了k 次转向的PDA 以及k 次转向的CFL,讨论了它们和S.Ginsburg 以空存储接受定义的2k-1次转向的PDA 以及2k-1次转向的CFL 之间的关系,给出了k 次转向的PDA 以及相应语言的一些性质.对于ω输入的情况,定义了以状态重复集接受和以空存储接受的有穷转向的ω—PDA以及相应的ω—CFL,证明了这两种接受方式识别同一语言类,并给出了有穷转向的ω—CFL 的若干性质.更多还原

【Abstract】 In this paper we defined k-turn PDA’s with the acceptance by termi-nal states and k-turn CFL’s.The relations between k-turn PDA’swith the acceptance by terminal states and by emptying store wereindicated.For the infinite inputting strings we defined(?)-finite-turnPDA’s with the acceptance by state repetition set and by emptying storeand their corresponding languages.Then we discussed the hierarchy inthe family of co-finite-turn CFL’s,several properties of(?)-finite-turnCFL’s and the relation between two accepting models.更多还原