Fuzzy state grammar and fuzzy deep pushdown automaton

Article type: Research Article

Authors: Kalra, Nidhi^* | Kumar, Ajay^*

Affiliations: Computer Science and Engineering Department, Thapar University, Patiala, Punjab, India

Correspondence: [*] Corresponding author: Nidhi Kalra and Ajay Kumar, Computer Science and Engineering Department, Thapar University, Patiala, Punjab, India. Tel.: +91 9501351188; E-mail: [email protected] (Nidhi Kalra) and Tel.: +91 9417192867; Fax: +91 175 2364498, 2393020; E-mail: [email protected] (Ajay Kumar).

Abstract: Motivated by the concept of fuzzy finite automata and fuzzy pushdown automata, we investigate a novel fuzzy state grammars and fuzzy deep pushdown automata concept. This concept represents a natural extension of contemporary state grammar and deep pushdown automaton, making them more robust in terms of imprecision, errors, and uncertainty. It has been proved that we can construct fuzzy deep pushdown automata from fuzzy state grammars and vice-versa. Furthermore, it has been proved that if fuzzy deep pushdown automaton Mfd is constructed from fuzzy state grammar Gfs then L (Mfd) = L (Gfs). In other words, for any string α ∈ Σ*, μ (α ; α ∈ L (Gfs)) = μ (α ; α ∈ L (Mfd)) where μ denotes the membership of a string.

Keywords: Regulated grammars, regulated automata, fuzzy state grammars, fuzzy deep pushdown automata

DOI: 10.3233/IFS-162138

Journal: Journal of Intelligent & Fuzzy Systems, vol. 31, no. 1, pp. 249-258, 2016