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.
DassowJ. and PawnG., Regulated rewriting in formal language theory, Springer Publishing Company,
2012.
2.
DassowJ., Grammars with regulated rewriting, Formal Languages and Applications, Studies in Fuzziness and Soft Computing 148, SpringerBerlin Heidelberg, pp. 2004, 249–273.
3.
MedunaA., Formal Languages and Computation: Models and their applications, CRC Press, 2014.
4.
KumarA. and VermaA.K., An improved algorithm for the metamorphosis of semi-extended regular expressions to deterministic finite automata, The Computer Journal58 (2015), 448–456.
5.
KumarA. and VermaA.K., A novel algorithm for the conversion of parallel regular expressions to non-deterministic finite automata, Applied Mathematics & InformationSciences8(1) (2014), 95–105.
6.
LiY. and PedryczW., Fuzzy finite automata and fuzzy regular expressions with membership values in lattice-ordered monoids, Fuzzy Sets and Systems156(1) (2005), 68–92.
7.
MoragaC., An approach to fuzzy context-free languages, In: XIV Sanish Congress on Fuzzy Logic Technologies, Langreo-Mires, 2008, pp. 73–78.
8.
AsveldP.R.J., Controlled Fuzzy parallel rewriting in: New Trends in Formal Languages—Control, Cooeration, and Combinatorics 1218, Springer-Verlag, 1997, pp. 49–70.
9.
AsveldP.R.J., The non-self-embedding property for generalized fuzzy context-free grammars, Publicationes Mathematicae Debrecen54(Suppl 1) (1999), 553–573.
LeeE.T. and ZadehL.A., Note on fuzzy languages, Information Sciences1(4) (1969), 421–434.
12.
WangH. and QiuD., Computing with words via Turing machines: A formal approach, IEEE Transactions on Fuzzy System11(6) (2003), 742–753.
13.
KasaiT., An hierarchy between context-free and context-sensitive languages, Journal of Computer and System Sciences4(5) (1970), 492–508.
14.
MedunaA., Deep pushdown automata, Acta Informatica42(8-9) (2006), 541–552.
15.
SolarP. and MedunaA., Deep Pushdown Transducers and State Translation Schemes, Brno University of Technology, In Proceedings of the 20th Conference STUDENT EEICT2014, pp. 264–268.
16.
AsveldP.R.J., Fuzzy context-free languages Part 1: Generalized fuzzy context-free grammars, Theoretical Computer Science347(1) (2005), 167–190.
17.
AsveldP.R.J., Fuzzy context-free languages Part 2: Recognition and parsing algorithms, Theoretical Computer Science347(1) (2005), 191–213.
18.
SchneiderM., LimH. and ShoaffW., The utilization of fuzzy sets in the recognition of imperfect strings, Fuzzy Sets and Systems49(3) (1992), 331–337.
19.
InuiM., ShoaffW., FausettL. and SchneiderM., The recognition of imperfect strings generated by fuzzy context-sensitive grammars, Fuzzy Sets and Systems62(1) (1994), 21–29.
20.
XingH., Fuzzy pushdown automata, Fuzzy Sets and Systems158(13) (2007), 1437–1449.
21.
BucurescuI. and PascuA., Fuzzy pushdown automata, International Journal of Computer Mathematics10(2) (1981), 109–119.
22.
HopcroftJ.E., MotwaniR. and UllmanJ.D., Introduction to Automata Theory, Languages and Computation, Pearson Education, Singapore, 2000.
23.
RosenkrantzD.J., Programmed grammars and classes of formal languages, Journal of the ACM16(1) (1969), 107–131.
24.
CremersA.B. and MayerO., On matrix languages, Information and Control23(1) (1973), 86–96.
25.
GinsburgS. and SpanierE.H., Control sets on grammars, Mathematical Systems Theory2(2) (1968), 159–177.
26.
MedunaA., Generalized forbidding grammars, International Journal of Computer Mathematics36(1-2) (1990), 31–38.
27.
ZemekP., One-sided random context grammars: Established results and open problems, In Proceedings of the 19th Conference STUDENT EEICT3 (2013), 222–226.
28.
PaunG., A variant of random context grammars: i-conditional grammars, Theoretical Computer Science41 (1985), 1–17Sem.
29.
MedunaA. and ZemekP., One-sided random context grammars with a limited number of right random context rules, Theoretical Computer Science516 (2014), 127–132.
30.
MedunaA. and ZemekP., One-sided forbidding grammars and selective substitution grammars, International Journal of Computer Mathematics89(5) (2012), 586–596.
31.
MedunaA. and ZemekP., Generalized one-sided forbidding grammars, International Journal of Computer Mathematics90(2) (2013), 172–182.
32.
CaoY. and EzawaY., Nondeterministic fuzzy automata, Information Sciences191 (2012), 86–97.
