Journal of Applied Mathematics
Volume 2013 (2013), Article ID 825249, 16 pages
Research Article

On Intuitionistic Fuzzy Context-Free Languages

1College of Mathematics and Econometrics, Hunan University, Changsha 410082, China
2College of Sciences, Southwest Petroleum University, Chengdu 610500, China

Received 19 October 2012; Revised 15 December 2012; Accepted 15 December 2012

Academic Editor: Hak-Keung Lam

Copyright © 2013 Jianhua Jin et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


Taking intuitionistic fuzzy sets as the structures of truth values, we propose the notions of intuitionistic fuzzy context-free grammars (IFCFGs, for short) and pushdown automata with final states (IFPDAs). Then we investigate algebraic characterization of intuitionistic fuzzy recognizable languages including decomposition form and representation theorem. By introducing the generalized subset construction method, we show that IFPDAs are equivalent to their simple form, called intuitionistic fuzzy simple pushdown automata (IF-SPDAs), and then prove that intuitionistic fuzzy recognizable step functions are the same as those accepted by IFPDAs. It follows that intuitionistic fuzzy pushdown automata with empty stack and IFPDAs are equivalent by classical automata theory. Additionally, we introduce the concepts of Chomsky normal form grammar (IFCNF) and Greibach normal form grammar (IFGNF) based on intuitionistic fuzzy sets. The results of our study indicate that intuitionistic fuzzy context-free languages generated by IFCFGs are equivalent to those generated by IFGNFs and IFCNFs, respectively, and they are also equivalent to intuitionistic fuzzy recognizable step functions. Then some operations on the family of intuitionistic fuzzy context-free languages are discussed. Finally, pumping lemma for intuitionistic fuzzy context-free languages is investigated.