Characterization of ω-Type Context-Free Languages by Means of Stack Run
信行 高橋 · Institutional Repositories DataBase (IRDB) · 1984
ω-type context-free languages are ω-type languages generated by ω-type context-free grammers, and also can be characterized in terms of nondeterministic pushdown automata running on infinite tapes. The paper discusses property of the class of ω-type context-free languages, CFL_ω, in view of the function of pushdown stack of the machines. So we review the concept of CFL_ω, and then compare with the property of words accepted by ω-type pushdown automata proposed in this paper and the property of words in ω-type context-free languages. Consequently it's found out that there exists functional equivalency between these stack run and ordinary state run. In other words, we argue that the class of languages characterized with stack run of 3-acceptance and the class of languages characterized with stack run of 2-acceptance are equivalent and as a result these classes coincide with CFL_ω.