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: kalranidhi8@gmail.com (Nidhi Kalra) and Tel.: +91 9417192867; Fax: +91 175 2364498, 2393020; E-mail: ajayloura@gmail.com (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
