Algebraic characterizations of context-free languages based on Lukasiewicz logic
Han Zhaoyin · Computer Engineering and Applications Journal · 2011
This paper introduces,the notion Lukasiewicz lattice-valued pushdown automaton(l-VPDA),traverses some algebraic properties of these automata in details and also establishes the algebraic features of these automata,i.e,by using the means of fuzzy state construction,and proves the fact that an arbitrary l-VPDA which accepts the l-valued language by final states and the other l-VPDA with the crisp transition relation and fuzzy final states are equivalently constructed,and also shows that an arbitrary l-VPDA can accept the same l-valued language by empty stack and by one l-VPDA with the crisp transition relation except one step with fuzzy transition relation in the mean time.It also discusses some algebraic and level characterizations of l-valued context-free languages,and deals with the closed properties of these l-valued languages under some regular operations in particular at the same time.