Fuzzy state grammar and fuzzy deep pushdown automaton

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 M_fd is constructed from fuzzy state grammar G_fs then L (M_fd) = L (G_fs). In other words, for any string α ∈ Σ^*, μ (α ; α ∈ L (G_fs)) = μ (α ; α ∈ L (M_fd)) where μ denotes the membership of a string.

Keywords

Regulated grammars regulated automata fuzzy state grammars fuzzy deep pushdown automata

1 Introduction

Context-free grammars are incapable of encapsulating all natural language phenomena. Context-sensitive grammars can be used to represent natural languages consisting of nested and interleaved dependencies. Notwithstanding, these context-sensitive grammars suffer from several drawbacks (e.g., membership and emptiness problems). To overcome the limitations of context-free and context-sensitive grammars, regulated grammars have been proposed. Regulated grammar [1 –3] is an extension of context-free grammar with some regulations, and it is used to represent nested and interleaved dependencies.

In formal language [4–5], input string can either be accepted (μ_w = 1) or rejected (μ_w = 0). Fuzziness has been introduced into regulated grammar in order to close the gap between the polar accept and reject extremes, and to make the grammar more robust. However, a robust parser may be required in the event of errors being present in the input. The input string will belong to a language with some certainty between 0 and 1. Motivated by the similarities between fuzzy finite automata [6] and fuzzy pushdown automata [7], this paper explores the concepts of fuzzy regulated grammar and fuzzy regulated automata. The need and importance of developing fuzzy languages and fuzzy automata has been explored previously in the literature [8 –12].

In this paper, concepts of fuzzy state grammar and fuzzy deep pushdown automaton are introduced. Fuzzy state grammar is a generalization of state grammar, whereas a fuzzy deep pushdown automaton is a generalization of deep pushdown automaton. It is shown that fuzzy deep pushdown automaton can accept fuzzy state grammar and vice-versa.

Prior Work: Kasai [13] first introduced the concept of state grammar. Meduna [14] later proposed deep pushdown automata as an extension of traditional pushdown automata with the additional capability of being able to push symbols onto the deeper parts of a stack. Deep pushdown automata are the formal models used for representing n-limited state grammars. Solar and Meduna [15] proposed state translation schemes and deep pushdown transducers, which are extensions of state grammar and deep pushdown automaton, capable of producing two output strings in one derivation.

Asveld [16] proposed fuzzy context-free K-grammar to represent erroneous sentences. Asveld [17] proposed a modified Cocke-Younger-Kasami (CYK) algorithm to recognize fuzzy context-free grammar. Schinder et al. [18] described an approach for recognizing imperfect strings generated by the context-free grammar. Similarly, Inui et al. [19] designed an algorithm for recognizing imperfect strings generated by the context-sensitive grammar. The idea that errors were possible in context-free and context-sensitive grammars was proposed by Schneider et al. [18–19] and Asveld [16]. In this paper, we propose a similar method with respect to state grammar.

Xing [20] proposed one-stack fuzzy pushdown automata and multi-stack fuzzy pushdown automata; demonstrating that the languages generated by one stack fuzzy push down automata, multi-stack fuzzy push down automata, and fuzzy context-free k-languages constituted fuzzy context-free grammars. Bucurescu and Pascu [21] proposed the concept of fuzzy pushdown automata and Boolean fuzzy pushdown automata. In fuzzy pushdown automata, weights are assigned in the interval [1], and it accepts context-free language. In Boolean fuzzy pushdown automata, weights are assigned using boolean algebra, and it accepts context-sensitive language. In this paper, we describe the use of initial state, pushdown, and final state distributions as defined by Bucurescu and Pascu [21]. Moraga [7] defines the relationship between fuzzy context-free languages and fuzzy pushdown automata, calculating the degree of membership based on weights as determined by a monoid. Hopcroft et al. [22] demonstrate the equivalence between pushdown automata and context-free grammars. In this paper, a similar methodology is used to prove the equivalence between the fuzzy deep pushdown automata and state grammars.

Contributions: After introducing some preliminary concepts in Section 2, following contributions are claimed:

A novel concept of fuzzy state grammar has been introduced in Section 3.

In Section 4, the concept of fuzzy deep pushdown automata has been proposed.

In Section 5, equivalence between fuzzy deep pushdown automata and fuzzy state grammars has been introduced.

We conclude in Section 6.

2 Preliminaries

Before turning to fuzzy state grammars and fuzzy deep pushdown automata, we must first define terms and notations. Let ∑ be an alphabet consisting of a finite set of terminals. ɛ denotes empty string. G denotes the grammar. L (G) denotes the language generated by grammar G. μ_L (α) denotes the membership grade of string α in the language L. Operator _ is used to replace a symbol by any arbitrary symbol from alphabet ∑. Throughout this paper, push operations are represented by ⇒_e, and ⇒_p is used to represent pop operations.

Definition 2.1. Regulated grammar [1 –3] is quintuple (N, ∑, S, P, RG) where,

N is set of non-terminals,

∑ is set of terminals,

S is the start symbol,

P is the set of production rules, and

RG is the restriction applied on the derivations of strings.

RG depends on the type of regulated grammar.

Regulated grammars are classified into rule-based [13 , 23–25] and context-based grammatical regulation [26 –31] as shown in Fig. 1. A state grammar is a rule-based grammatical regulation, in which control regulation are presented in term of states. The current state determines which rule to be applied next.

Definition 2.2. A state grammar [13] is a pentuple G_s = (V, Q, Σ, P, S), where

V is a finite set of symbols;

Q is a finite set of states, and V ∩ Q = φ;

Σ ⊂ V is an alphabet of terminals;

S ∈ V - Σ is the start symbol.

P ⊆ (Q × (V - Σ) × (Q × V⁺)) is a finite relation over the productions.

Example 2.1. Suppose the state grammar G₁ [3] with the production P is defined as follows: $\begin{matrix} G_{1} = {{S, X, Y, 0, 1}, \\ {{pr}_{0}, {pr}_{1}, {pr}_{2}, {pr}_{3}, {pr}_{4}, {pr}_{5}}, {0, 1}, P, S} \\ ({pr}_{0}, S) \to ({pr}_{0}, XY) \\ ({pr}_{0}, X) \to ({pr}_{1}, 0 X) ({pr}_{1}, Y) \to ({pr}_{0}, 0 Y) \\ ({pr}_{0}, X) \to ({pr}_{2}, 1 X) ({pr}_{2}, Y) \to ({pr}_{0}, 1 Y) \\ ({pr}_{0}, X) \to ({pr}_{3}, 0) ({pr}_{3}, Y) \to ({pr}_{0}, 0) \\ ({pr}_{0}, X) \to ({pr}_{4}, 1) ({pr}_{4}, Y) \to ({pr}_{0}, 1) \end{matrix}$

Given input string w = 010010 $\begin{matrix} S_{p_{0}} \to {XY}_{p_{0}} \to 0 {XY}_{p_{1}} \to 0 X 0 Y_{p_{0}} \to 01 X 0 Y_{p_{2}} \to \\ 01 X 01 Y_{p_{0}} \to 01001 Y_{p_{3}} \to 010010_{p_{0}} \end{matrix}$

The non-context-free language generated by G₁ is L (G₁) = {ww|w ∈ {0, 1} ⁺}.

Definition 2.3. A deep pushdown automaton [14] is a septuplet M = (Q, Γ, ∑, R, q₀, S, F) where

Q is a finite set of states,

Γ is a pushdown alphabet,

∑ is an input alphabet such that ∑ ⊆ Γ and Γ - ∑ = {#},

R is a finite relation such that $\begin{matrix} R \subseteq (I \times Q \times (Γ \times (\sum \cup {#})) \times Q \\ \times (Γ - {#})^{+}) \cup (I \times Q \times {#} \end{matrix}$ and the elements of {I , Q, Γ} are pair-wise disjoint where I denotes natural numbers.

q₀ ∈ S denotes the starting state,

S ∈ Γ is the start pushdown symbol,

F ∈ Q is the set of final states.

A configuration of M is a triple in Q × ∑^* × (Γ - {#}) ^* {#}

Example 2.2. Consider a deep pushdown automaton,

₂M = ({q₀, p, q, s′, t} , {0, 1} , {X, S, #} , R, q₀, S, {s′, t}) with R containing rules $\begin{matrix} 1 q_{0} S \to pXX \\ 1 pX \to q 0 X 2 qX \to p 0 X \\ 1 pX \to r 1 X 2 rX \to p 1 X \\ 1 pX \to s^{'} 0 s^{'} X \to s^{'} 0 \\ 1 pX \to t 1 tX \to t 1 \end{matrix}$

For input string α = 010010 $\begin{matrix} (q_{0}, 010010, S #) \Rightarrow_{e} (p, 010010, XX #) \\ \Rightarrow_{e} (q, 010010, 0 XX #) [1 pX \to q 0 X] \\ \Rightarrow_{p} (q, 10010, XX #) \\ \Rightarrow_{e} (p, 10010, X 0 X #) [2 qX \to p 0 X] \\ \Rightarrow_{e} (r, 10010, 1 X 0 X #) [1 pX \to r 1 X] \\ \Rightarrow_{p} (r, 0010, X 0 X #) \\ \Rightarrow_{e} (p, 0010, X 01 X #) [2 rX \to p 1 X] \\ \Rightarrow_{e} (s^{'}, 0010, 001 X #) [1 pX \to s^{'} 0] \\ \Rightarrow_{p} (s^{'}, 010, 01 X #) \\ \Rightarrow_{p} (s^{'}, 10, 1 X #) \\ \Rightarrow_{p} (s^{'}, 0, X #) \\ \Rightarrow_{e} (s^{'}, 0, 0 #) [s^{'} X \to s^{'} 0] \\ \Rightarrow_{p} (s^{'}, ɛ, #) \end{matrix}$

In brief $(q_{0}, 010010, S #) \overset{*}{\Rightarrow} (f, ɛ, #)$ . Here f = {s′, t}. Hence, the language accepted by deep pushdown automataon is L (₂M) = {ww|w ∈ {0, 1} ⁺}.

Definition 2.4. A fuzzy grammar [11] is a quadruple (V, Σ, P, S), where

V is a set of non-terminals,

Σ is a set of terminals,

P is a set of fuzzy productions of the form $A \overset{μ}{\to} B | A, B \in (V \cup Σ)^{*} \land μ : P \to [0, 1]$ and

S ∈ V_N is a start symbol

Definition 2.5. A fuzzy automaton [32] is a quintuple (Q, ∑, q₀, δ, F), where

Q is the set of states,

∑ is input alphabet,

q₀ ∈ Q is initial state,

δ is a fuzzy transition function mapping, Q × ∑ → f (Q). For q ∈ Q, f (q) denotes the degree of membership with which q to be a final state, and

F ⊆ f (Q) is the set of fuzzy final states.

3 Fuzzy state grammar

In this section, we introduce the concept of fuzzy state grammar.

Definition 3.1. A fuzzy state grammar G_fs is septuple (V, Q, Σ, P, S, E, μ), where

(V, Q, Σ, P, S} is a state grammar,

E is the set of error productions, and

μ : P → [0, 1] is a weighting function. The set {(p, μ (p)) |p ∈ P} constitutes a fuzzy set of productions.

Definition 3.2. A fuzzy state language is given by the triple (G, min , max) where G is a fuzzy state grammar. Degree of membership of a string is calculated using the min operation. Min operation is applied to the weights of all productions used to derive a particular string from the initial symbol.

It holds: μ_L(G) (α) = min(μ (p_i) , μ (p_j) , …, μ (p_z)) Equation (1)

where p_i, p_j, …, p_z ∈ P are productions used to derive the string α.

If the grammar is ambiguous, then different degrees of membership obtained for the string α using different sequences of productions. Max operation is applied to determine the best membership for the string.

μ_L(G) (α) = max {min(μ (p_i) , μ (p_j) , …, μ (p_z))} Equation (2)

Example 3.1. Consider the fuzzy stategrammar G_fs = ({S, A, B, a, b} , {p₀, p₁, p₂, p₃, p₄, p₅} , {a, b} , P, S, E, μ), where E is the set of error productions, μ is the weighting function μ : P → [0, 1] is a weighting function.

The set {(p, μ (p)) |p ∈ P} constitutes a fuzzy set of productions with the following rules in P: $\begin{matrix} (p_{0}, S) \overset{1}{\to} (p_{0}, AB) \\ (p_{0}, A) \overset{1}{\to} (p_{1}, aAb) (p_{1}, B) \overset{1}{\to} (p_{0}, Bc) \\ (p_{0}, A) \overset{1}{\to} (p_{2}, ab) (p_{2}, B) \overset{1}{\to} (p_{0}, c) \end{matrix}$

The language generated L (G_fs) = {aⁿbⁿcⁿ|n ≥ 1}.

Errors in the input string are classified into following three types:

Replacement Error: In replacement error [18–19], a terminal is substituted with another terminal symbol from the set ∑. The certainty of occurrence of replacement error is maximum as tested from different erroneous input dataset. Hence the membership grade of replacement error is 0.6.

Addition Error: In addition error [18–19], an extra new terminal symbol is added from the terminal set ∑. An extra new terminal can be placed before or after the terminal. The certainty of addition error occurrence is minimum with membership grade 0.3.

Removal Error: In removal error [18–19], some terminal is deleted. The membership grade of removal error is 0.4.

The set of error productions E is as follows:

1. On applying replacement error: (Here _– denotes that it can be replaced by any arbitrary symbol from alphabet ∑) $\begin{matrix} (p_{0}, A) \overset{0.6}{\to} (p_{1}, -_{Ab}) \\ (p_{0}, A) \overset{0.6}{\to} (p_{1}, {aA}_{-}) \\ (p_{0}, A) \overset{0.6}{\to} (p_{1},_{-} A_{-}) \\ (p_{1}, B) \overset{0.6}{\to} (p_{0}, B_{-}) \\ (p_{0}, A) \overset{0.6}{\to} (p_{2},_{-} b) \\ (p_{0}, A) \overset{0.6}{\to} (p_{2}, a_{-}) \\ (p_{0}, A) \overset{0.6}{\to} (p_{2},_{-}_{-}) \\ (p_{2}, B) \overset{0.6}{\to} (p_{0},_{-}) \end{matrix}$

2. On applying addition error: $\begin{matrix} (p_{0}, A) \overset{0.3}{\to} (p_{1},_{-} a_{-} A b) \\ (p_{0}, A) \overset{0.3}{\to} (p_{1}, {aA}_{-} b_{-}) \\ (p_{0}, A) \overset{0.3}{\to} (p_{1},_{-} a_{-} A_{-} b_{-}) \\ (p_{1}, B) \overset{0.3}{\to} (p_{0}, B_{-} c_{-}) \\ (p_{0}, A) \overset{0.3}{\to} (p_{2},_{-} a_{-} b) \\ (p_{0}, A) \overset{0.3}{\to} (p_{2}, a_{-} b_{-}) \\ (p_{0}, A) \overset{0.3}{\to} (p_{2},_{-} {a_{-}}_{-} b_{-}) \\ (p_{2}, B) \overset{0.3}{\to} (p_{0},_{-} c_{-}) \end{matrix}$

3. On applying removal error: $\begin{matrix} (p_{0}, A) \overset{0.4}{\to} (p_{1}, Ab) \\ (p_{0}, A) \overset{0.4}{\to} (p_{1}, aA) \\ (p_{0}, A) \overset{0.4}{\to} (p_{1}, A) \\ (p_{1}, B) \overset{0.4}{\to} (p_{0}, B) \\ (p_{0}, A) \overset{0.4}{\to} (p_{2}, b) \\ (p_{0}, A) \overset{0.4}{\to} (p_{2}, a) \\ (p_{0}, A) \overset{0.4}{\to} (p_{2}, ɛ) \\ (p_{2}, B) \overset{0.4}{\to} (p_{0}, ɛ) \end{matrix}$

Consider unambiguous erroneous string α = abbbcc such that α ∉ L $\begin{matrix} S_{p_{0}} \overset{1}{\to} {AB}_{p_{0}} \overset{1}{\to} {aAbB}_{p_{1}} \overset{1}{\to} {aAbBc}_{p_{0}} \overset{0.6}{\to} {abbbBc}_{p_{2}} \\ \overset{1}{\to} {abbbcc}_{p_{0}} \\ μ (abbbcc) = min (1; 1; 1; 0.6; 1) \\ = 0.6 \end{matrix}$

Consider ambiguous erroneous string α = aabacc such that α ∉ L

Derivation 1: $S_{p_{0}} \overset{1}{\to} {AB}_{p_{0}} \overset{0.6}{\to} {aAaB}_{p_{1}} \overset{1}{\to} aAa$ ${Bc}_{p_{0}} \overset{1}{\to} {aabaBc}_{p_{2}} \overset{1}{\to} {aabacc}_{p_{0}}$ $μ (aabacc) = min (1; 0.6; 1; 1; 1) = 0.6$

Derivation 2: $S_{p_{0}} \overset{1}{\to} {AB}_{p_{0}} \overset{0.3}{\to} {aAbaB}_{p_{1}} \overset{1}{\to} aAba$ ${Bc}_{p_{0}} \overset{0.4}{\to} {aabaBc}_{p_{2}} \overset{1}{\to} {aabacc}_{p_{0}}$ $μ (aabacc) = min (1; 0.3; 1; 0.4; 1) = 0.4$

The membership of erroneous string α = aabacc is:

max(min(Derivation 1, Derivation 2) =max(0.6 ; 0.3) = 0.6

Hence derivation 1 is the optimal derivation with membership grade μ = 0.6.

4 Fuzzy deep pushdown automaton

In this section, we introduce the concept of fuzzy deep pushdown automaton.

Definiton 4.1. A fuzzy deep pushdown auto-maton (FDPDA) M_fd is a duodecuple (Q, ∑, Γ, R, q₀, S, F, E, μ, π, γ, η) where (Q, Γ, ∑, R, q₀, S, F) are as usual in deep pushdown automata [14] and

E is the error set of productions,

μ : P → [0, 1] is a weighting function,

The set {p, (μ (p)) |p ∈ P} consists of fuzzy productions of the form $Q \times Σ^{*} \times Γ^{*} \overset{μ}{\to} Q \times Γ^{*}$

π : Q → [0, 1] is an initial state function defined by

π (q) = (\begin{matrix} 1, & q = q_{0} \\ 0, & q \neq q_{0} \end{matrix})

γ : Γ → [0, 1] is a pushdown function defined by

γ (Γ) = (\begin{matrix} 1, & Γ = S \\ 0, & Γ \neq S \end{matrix})

η : Q → [0, 1] is a final state function, defined by

η (F) = (\begin{matrix} 1, & f \in F \\ 0, & f \notin F \end{matrix})

A configuration of M_fd is a triple in $Q \times \sum^{*} \times (Γ - {#})^{*} {#} \overset{μ}{\to} Q \times Γ^{*}$

Example 4.1. Let us consider fuzzy deep pushdown automaton M_fd = ({ q₀, q, p } , { a, b, c } , { A, S, # } , R, q₀, S, {F } , E, μ, π, γ, η) with R containing rules $\begin{matrix} δ (1, q_{0}, S) \overset{1}{\to} (q, AA), δ (1, q, A) \overset{1}{\to} (p, aAb) \\ δ (1, q, A) \overset{1}{\to} (f, ab), δ (2, p, A) \overset{1}{\to} (q, Ac) \\ δ (1, f, A) \overset{1}{\to} (f, c) \end{matrix}$

The set of error productions E are: $\begin{matrix} δ (1, q, A) \overset{0.6}{\to} (p,_{-} Ab) δ (1, q, A) \overset{0.6}{\to} (p, {aA}_{-}) \\ δ (1, q, A) \overset{0.6}{\to} (p,_{-} A_{-}) δ (1, q, A) \overset{0.3}{\to} (p,_{-} a_{-} Ab) \\ δ (1, q, A) \overset{0.3}{\to} (p,_{-} a_{-} A_{-} b_{-}) \\ δ (1, q, A) \overset{0.3}{\to} (p, {aA}_{-} b_{-}) \\ δ (1, q, A) \overset{0.4}{\to} (p, Ab) δ (1, q, A) \overset{0.4}{\to} (p, aA) \\ δ (1, q, A) \overset{0.4}{\to} (p, A) δ (2, p, A) \overset{0.6}{\to} (q, A_{-}) \\ δ (2, p, A) \overset{0.3}{\to} (q, A_{-} c_{-}) δ (2, p, A) \overset{0.4}{\to} (q, A) \\ δ (1, q, A) \overset{0.6}{\to} (f, a_{-}) δ (1, q, A) \overset{0.6}{\to} (f,_{-} b) \\ δ (1, q, A) \overset{0.6}{\to} (f,_{-}_{-}) δ (1, q, A) \overset{0.3}{\to} (f,_{-} a_{-} b) \\ δ (1, q, A) \overset{0.3}{\to} (f, a_{-} b_{-}) δ (1, q, A) \overset{0.3}{\to} (f,_{-} {a_{-}}_{-} b_{-}) \\ δ (1, q, A) \overset{0.4}{\to} (f, a) δ (1, q, A) \overset{0.4}{\to} (f, b) \\ δ (1, q, A) \overset{0.4}{\to} (f, ɛ) δ (1, f, A) \overset{0.6}{\to} (f,_{-}) \\ δ (1, f, A) \overset{0.3}{\to} (f,_{-} c_{-}) δ (1, f, A) \overset{0.4}{\to} (f, ɛ) \end{matrix}$

Pop operation is applied whenever the topmost symbol from the stack and current symbol under read-write head matches, keeping the state same and the membership value is 1 for this rule.

Consider unambiguous erroneous string α = abbbcc ∉ L $\begin{matrix} (q_{0}, abbbcc, S #) \Rightarrow_{e}^{1} (q, abbbcc, AA #) \\ \Rightarrow_{e}^{1} (p, abbbcc, aAbA #) \Rightarrow_{p}^{1} (p, bbbcc, AbA #) \\ \overset{1}{\Rightarrow_{e}} (q, bbbcc, AbAc #) \overset{0.6}{\Rightarrow_{e}} (f, bbbcc, bbbAc #) \\ \overset{1}{\Rightarrow_{p}} (f, bbcc, bbAc #) \overset{1}{\Rightarrow_{p}} (f, bcc, bAc #) \\ \overset{1}{\Rightarrow_{p}} (f, cc, Ac #) \overset{1}{\Rightarrow_{e}} (f, cc, cc #) \overset{1}{\Rightarrow_{p}} (f, c, c #) \\ \overset{1}{\Rightarrow_{p}} (f, ɛ, #) \\ μ (abbbcc) \\ = min (1; 1; 1; 1; 6; 1; 1; 1; 1; 1; 1) = 0.6 \end{matrix}$

Consider ambiguous erroneous string α =aabacc ∉ L

Derivation 1. $\begin{matrix} (q_{0}, aabacc, S #) \Rightarrow_{e}^{1} (q, aabacc, AA #) \\ \Rightarrow_{e}^{0.6} (p, aabacc, aAaA #) \Rightarrow_{p}^{1} (p, abacc, AaA #) \\ \Rightarrow_{e}^{1} (q, abacc, AaAc #) \Rightarrow_{e}^{1} (f, abacc, abaAc #) \\ \Rightarrow_{p}^{1} (f, bacc, baAc #) \Rightarrow_{p}^{1} (f, acc, aAc #) \\ \Rightarrow_{p}^{1} (f, cc, Ac #) \Rightarrow_{e}^{1} (f, cc, cc #) \Rightarrow_{p}^{1} (f, c, c #) \\ \Rightarrow_{p}^{1} (f, ɛ, #) \\ μ (aabacc) \\ = min (1; 0.6; 1; 1; 1; 1; 1; 1; 1; 1; 1) = 0.6 \end{matrix}$

Derivation 2. $\begin{matrix} (q_{0}, aabacc, S #) \Rightarrow_{e}^{1} (q, aabacc, AA #) \\ \Rightarrow_{e}^{0.3} (p, aabacc, aAbaA #) \Rightarrow_{p}^{1} (p, abacc, AbaA #) \\ \Rightarrow_{e}^{1} (q, abacc, AbaAc #) \Rightarrow_{e}^{0.4} (f, abacc, abaAc #) \\ \Rightarrow_{p}^{1} (f, bacc, baAc #) \Rightarrow_{p}^{1} (f, acc, aAc #) \\ \Rightarrow_{p}^{1} (f, cc, Ac #) \Rightarrow_{e}^{1} (f, cc, cc #) \Rightarrow_{p}^{1} (f, c, c #) \\ \Rightarrow_{p}^{1} (f, ɛ, #) \\ μ (aabacc) \\ = min (1; 0.3; 1; 1; 0.4; 1; 1; 1; 1; 1; 1) = 0.4 \end{matrix}$

The optimal derivation is max (derivation1; derivation 2) = max (0.6; 0.4) = 0.6.

4.1 Instantaneous description

The fuzzy deep pushdown automaton M_fd works similarly as deep pushdown automaton [14] except that for every rule some membership value is associated. Configuration or instantaneous description of M_fd is desribed by triple (q, α, T), where q, α, T denotes the current state, remaining input tape symbols and stack contents respectively.

Initial instantaneous description of M_fd is (q₀, α, S #), where q₀, α, S denotes the starting state, input string and stack starting symbol respectively. Move from one instantaneous description to another instantaneous description will be carried out by expansion or pop operation.

Consider ID₁ and ID₂ are two succesive instantaneous description of M_fd and we can move from ID₁ to ID₂ using the following two operations:

Pop operation: Consider ID₁ (p, bβ, bT) and ID₂ (p, β, T) are two instantaneous description such that p ∈ Q, b ∈ Σ, β ∈ Σ^* and T ∈ Γ^*. This operation is represented by ${ID}_{1} \Rightarrow_{p}^{μ_{i}} {ID}_{2}$ .

Expansion operation: Consider ID₁ (p, β, αAT) and ID₂ (q, β, αvT) are two succesive instantaneous description such that p, q ∈ Q, β ∈ Σ^*, α, T ∈ Γ^* and $(mpA \overset{μ_{i}}{\to} qv) \in R$ . It should be noted that α consists of (m - 1) non-terminals. This operation is represented by ${ID}_{1} \Rightarrow_{e}^{μ_{i}} {ID}_{2}$

5 Equivalence of fuzzy state grammarand fuzzy deep pushdown automaton

In this section, we discuss the equivalence between fuzzy state grammar and fuzzy deep pushdown automaton.

Theorem 1.LetG_fs (V, Q, Σ, P, S, E, μ) be a fuzzy state grammar, then we can construct a fuzzy deep pushdown automatonM_fd (Q, ∑, Γ, R, q₀, S, F, E, μ, π, γ, η) such thatL (G_fs) = L (M_fd) i.e. for anyα ∈ Σ^*, μ (α ; α ∈ L (G_fs)) = μ (α ; α ∈ L (M_fd)).

Proof. We can construct fuzzy deep pushdown automaton M_fd from fuzzy state grammar using the following procedure:

The distribution functions are defined by $π (q) = (\begin{matrix} 1, & q = q_{0} \\ 0, & q \neq q_{0} \end{matrix})$ $γ (Γ) = (\begin{matrix} 1, & Γ = S \\ 0, & Γ \neq S \end{matrix})$ $η (F) = (\begin{matrix} 1, & f \in F \\ 0, & f \notin F \end{matrix})$

Consider the production of starting symbol in the fuzzy state grammar $({pr}_{0}, S) \overset{μ_{i}}{\to} ({pr}_{0}, ABC \dots)$ , its corresponding equivalent fuzzy deep pushdown automaton rule is $1 {pr}_{0} S \overset{μ_{i}}{\to} {pr}_{0} XXX \dots$ . The depth of a rule in the fuzzy deep pushdown automaton depends on how much deep the non-terminal is presenting on the stack. For example, Consider $({pr}_{0}, S) \overset{μ_{i}}{\to} ({pr}_{0}, AB)$ production in the fuzzy state grammar, the corresponding starting state rule in fuzzy deep pushdown automaton will be $1 {pr}_{0} S \overset{μ_{i}}{\to} {pr}_{0} AA$ and the fuzzy deep pushdown automaton will be constructed of depth 2.

The transition function R is defined by

Given the production rule $(q_{0}, S) \overset{1}{\to} (p, α)$ in the fuzzy state grammar, add δ (1, q₀, $S) \overset{1}{\to} (p, α^{'})$ in R of M_fd such that α′ is equal to α except that all non-terminals of α are replaced by A in α′.

Given the production rule $(q, A) \overset{μ_{i}}{\to} (p, α)$ in the fuzzy state grammar, add δ (1, q, A) $\overset{μ_{i}}{\to} (p, α)$ in R of M_fd.

Given the production rule $(q, B) \overset{μ_{i}}{\to} (p, α)$ in the fuzzy state grammar, add δ (2, q, A) $\overset{μ_{i}}{\to} (p, α)$ in R of M_fd (As non-terminals of depth >1, we will replace the all non-terminal B of fuzzy state grammar to non-terminal A with depth 2 in fuzzy deep pushdown automaton.Similarly $δ (3, q, A) \overset{μ_{j}}{\to} (p, α)$ in R, if the rule $(q, C) \overset{μ_{j}}{\to} (p, α)$ is in fuzzy state grammar with membership grade μ_j and so on.

Pop operation is applied whenever the topmost symbol and the current symbol under read-write head matches, keeping the state same and the membership value is 1 for this rule.

Rigorous Proof. We want to prove that if $S_{q_{0}} \Rightarrow_{*}^{μ} w_{1} α$ then $(q_{0}, w_{1} w_{2}, S) \Rightarrow_{*}^{μ} (q, w_{2}, α^{'})$ for any w₂, where μ denotes degree of membership and α′ is equal to α except that all non-terminals of α are replaced by A in α′. $(q_{0}, S) \overset{1}{=} (q, γ_{1}) \overset{μ_{1}}{\Rightarrow} (q, γ_{2}) \overset{μ_{2}}{\Rightarrow} \dots \overset{μ_{n - 1}}{\Rightarrow} (q, γ_{n - 1}) = w$ such that μ (w) = min(1, μ₁, μ₂, … , μ_n-1) ∧ γ_i = w_iα_i. Here w_i is the string has already generated and α_i ∈ V^*.

Proof by Induction: This theorem is established by mathematical induction of n ≥ 0, where n represents the number of steps in the derivation of a string of a state grammar.

Basis Step: Consider n = 1, on applying the starting symbol production rule of the state grammar, a number of non-terminal are generated and no input symbol is generated i.e. w₁ = ɛ, w₂ = w and $(q_{0}, S) \overset{1}{\Rightarrow} (q, ɛ w_{2})$ such that w₂ ∈ (V - Σ) ^*.

Now $(q_{0}, w, S) \overset{1}{\Rightarrow} (q, w, α^{'})$ such that α′ is equal to w₂ except that all non-terminals of α are replaced by A in w₂. Hence it is true for n = 1.

Induction hypothesis: Assume that if (q₀, S) $\Rightarrow_{*}^{μ} (q, γ_{n})$ then $(q_{0}, w_{1} w_{2}, S) \Rightarrow_{*}^{μ} (q, w_{2}, α^{'})$ for any w₂ after n derivation from S, w₁ ∈ Σ^*, γ_n = w₁α, α ∈ V^*, α′ ∈ T*, μ = min(μ₁, μ₂, …, μ_n) and α′ is equal to α except that all non-terminals of α are replaced by A in α′.

Induction step: Now consider (n + 1) th derivation

If $(q_{0}, S) \Rightarrow_{*}^{μ} (q, γ_{n}) \overset{μ_{n + 1}}{\Rightarrow} (p, γ_{n + 1})$

Here γ_n = w₁α such that w₁ ∈ Σ^* and α ∈ V^*.

Following cases can occur:

Case 1: Consider in (n + 1) th derivation step, the leftmost non-terminal is replaced by a single terminal.

α = Aα₁ and $\begin{matrix} (q_{0}, S) \Rightarrow_{*}^{μ} (q, γ_{n}) = (q, w_{1} α) = (q, w_{1} A α_{1}) \\ \overset{μ_{n + 1}}{\Rightarrow} (p, w_{1} a α_{1}) = (p, γ_{n + 1}) \end{matrix}$ If the left non-terminal of α is A, then correspondingly in fuzzy deep pushdown automaton rule of 1 depth is applied. Using the 2nd rule of the construction of fuzzy deep pushdown automaton from fuzzy state grammar, we get $(q_{0}, w_{1} w_{2}, S) \Rightarrow_{*}^{μ} (q, w_{2}, α^{'}) \overset{μ_{n + 1}}{\Rightarrow} (q, w_{2}, α α^{″})$ .

Symbol a is popped from the stack and the same is read from w₂.

Here γ_n+1 = w₁aα₁ where w₁a ∈ Σ^* and denote the already consumed string. Similarly, if the left most non-terminal A gives a number of terminals, these will be popped from the stack and consumed from the input tape. Hence the property holds for (n + 1) derivation steps.

Case 2: Consider in (n + 1) th derivation step, (q, A) → (p, β) such that β ∈ V^*. $\begin{matrix} (q_{0}, S) \Rightarrow_{*}^{μ} (q, γ_{n}) = (q, w_{1} α) = (q, w_{1} A α_{1}) \\ \overset{μ_{n + 1}}{\Rightarrow} (p, w_{1} β α_{1}) = (p, γ_{n + 1}) \end{matrix}$

Case 3: Consider in (n + 1) th derivation step, (q, B) → (p, β) such that β ∈ V^*. $\begin{matrix} (q_{0}, S) \Rightarrow_{*}^{μ} (q, γ_{n}) = (q, w_{1} α) = (q, w_{1} A α_{1} B α_{1}) \\ \overset{μ_{n + 1}}{\Rightarrow} (p, w_{1} A α_{1} β α_{1}) = (p, γ_{n + 1}), \end{matrix}$ here α = Aα₁Bα₁, γ_n+1 = w₁Aα₁βα₁

If the non-terminal is B in fuzzy state grammar, so using the 3rd rule of the construction of fuzzy deep pushdown automaton from fuzzy state grammar, then correspondingly in fuzzy deep pushdown automaton rule of 2 depth is applied here α = Aα₁Aα₁ and $α^{″} = A α_{1} β α_{1}$ $(q_{0}, w_{1} w_{2}, S) \Rightarrow_{*}^{μ} (q, w_{1} w_{2}, α^{'}) \overset{μ_{n + 1}}{\Rightarrow}$ $(q, w_{1} w_{2}, α^{″}) .$

Case 4: Consider in (n + 1) ^th derivation step, (q, C) → (p, β) such that β ∈ V^*. $\begin{matrix} (q_{0}, S) \Rightarrow_{*}^{μ} (q, γ_{n}) = (q, w_{1} α) = (q, w_{1} A α_{1} B α_{1} C α_{1}) \\ \overset{μ_{n + 1}}{\Rightarrow} (p, w_{1} A α_{1} B α_{1} β α_{1}) = (p, γ_{n + 1}), \end{matrix}$ Here α = Aα₁Bα₁Cα₁, γ_n+1 = w₁Aα₁Bα₁βα₁

If the non-terminal is C in fuzzy state grammar, so using the 3rd rule of the construction of fuzzy deep pushdown automaton from fuzzy state grammar, then correspondingly in fuzzy deep pushdown automaton rule of 3 depth is applied here α = Aα₁Aα₁Aα₁ and $\begin{matrix} α^{''} = A α_{1} β α_{1} \\ (q_{0}, w_{1} w_{2}, S) \Rightarrow_{*}^{μ} (q, w_{1} w_{2}, α^{'}) \overset{μ_{n + 1}}{\Rightarrow} (q, w_{1} w_{2}, α^{''}) \end{matrix}$ Hence the same process is true for all the non-terminals in fuzzy state grammar. This completes the proof.

Theorem 2.LetM_fd (Q, ∑, Γ, R, q₀, S, F, E, μ, π, γ, η) be a fuzzy deep pushdown automaton, then we can construct be a fuzzy state grammarG_fs (V, Q, Σ, P, S, E, μ) such thatL (G_fs) = L (M_fd) i.e. for anyα ∈ Σ^*, μ (α ; α ∈ L (G_fs)) = μ (α ; α ∈ L (M_fd)) whereμdenotes the membership of a string.

Proof. We shall construct a fuzzy state grammar G_fs (V, Q, Σ, P, S, E, μ) grammar, where V = Σ ∪ Γ ∪ S and the production rules P are defined as follows:

If $δ (1, q, S) \overset{μ}{\to} (p, AA \dots)$ , then add the production $(q, S) \overset{μ}{\to} (q, AB \dots)$ in P. The depth of M_fd determines the number of different symbol expanded from the starting symbol of state grammar.

If $δ (1, q, A) \overset{μ}{\to} (p, β)$ , then add the production $(q, A) \overset{μ}{\to} (p, β)$ in P.

If $δ (2, q, A) \overset{μ}{\to} (p, β)$ , then add the production $(q, B) \overset{μ}{\to} (p, β)$ in P.

If $δ (3, q, A) \overset{μ}{\to} (p, β)$ , then add the production $(q, C) \overset{μ}{\to} (p, β)$ in P. The same process is repeated for depth >3.

We want to prove that if $(q_{0}, w_{1} w_{2}, S) \Rightarrow_{*}^{μ} (q, w_{2}, α)$ for any w₂ then $S_{q_{0}} \Rightarrow_{*}^{μ} w_{1} α$ , where denotes degree of membership.

Rigorous Proof. This theorem is established by induction of n ≥ 0, where n represents the number of moves made by the fuzzy deep pushdown automata.

Basis Step: The following two cases can occur:

Case 1: For n = 0, $(q_{0}, w, S) \Rightarrow_{*}^{μ} (q_{0}, w, S)$

Here α = S, w₁ = ɛ and $S_{q_{0}} \Rightarrow_{*}^{μ} S$ is always true.

Case 2: For n = 1, first moves is made by applying the transition function $δ (1, q_{0}, S) \overset{1}{\to} (p, α^{'})$

Hence $(q_{0}, w, S) \overset{1}{\Rightarrow} (q_{0}, w, α^{'})$

Here α′ is equal to α except that all non-terminals of α are replaced by A in α′, w₁ = ɛ and $S_{q_{0}} \overset{1}{\Rightarrow} α$ is surely true.

Induction hypothesis: Assume that (q₀, w₁w₂, $S) \Rightarrow_{*}^{μ} (q, w_{2}, α)$ for any w₂ if $S_{q_{0}} \Rightarrow_{*}^{μ} w_{1} α$ works for n - 1 moves in fuzzy deep pushdown automaton M_fd.

Induction step: Consider after n moves M_fd : $(q_{0}, w_{1} w_{2}, S) \Rightarrow_{*}^{μ} (q, w_{2}, α)$ , such that μ =min(μ₁, μ₂, … , μ_n) where μ₁, μ₂, … , μ_n denotes the degree of membership in each respective moves. The following three cases can occur using transition rules 2, 3 and 4 as mentioned above.

Case 1: Consider the nth moves occur due to pop operation. $(q_{0}, w_{1} {aw}_{2}, S) \Rightarrow_{*}^{μ} (q, {aw}_{2}, a α) \Rightarrow^{1} (q, w_{2}, α)$ where w = w₁a

Hence $(q_{0}, w_{1} {aw}_{2}, S) \Rightarrow_{*}^{μ} (q, w_{2}, β)$ then using the induction hypothesis, $(q_{0}, w_{1} {aw}_{2}, S) \Rightarrow_{*}^{μ} (q, {aw}_{2}, a α)$ means $S_{q_{0}} \Rightarrow_{*}^{μ} w_{1} a α$ after n - 1 moves, but w = w₁a hence $S_{q_{0}} \Rightarrow_{*}^{μ} w α$ with membership min (μ, 1) = μ.

Case 2: Consider the nth move occur due to the rule $δ (1, q, A) \overset{μ_{n}}{\to} (p, α)$ $(q_{0}, w_{1} w_{2}, S) \Rightarrow_{*}^{μ} (q, w_{2}, A α) \Rightarrow^{μ_{n}} (p, w_{2}, γ α)$ where β = γα

Using induction hypothesis, $(q_{0}, w_{1} w_{2}, S) \Rightarrow_{*}^{μ} (q, w_{2}, A α)$ means $S_{q_{0}} \Rightarrow_{*}^{μ} w_{1} A α$ , thus $S_{q_{0}} \Rightarrow_{*}^{μ} w_{1} γ α = w_{1} β$ with membership min (μ, μ_n).

Case 3: Consider the nth move occur due to the rule $δ (m, q, A) \overset{μ_{n}}{\to} (p, γ)$ where m = 2, γ ∈ Γ^*.

$(q_{0}, w_{1} w_{2}, S) \Rightarrow_{*}^{μ} (q, w_{2}, α A β) \Rightarrow^{μ_{n}} (p, w_{2}, α γ β)$ where w = αγβ

Using induction Hypothesis $(q_{0}, w_{1} w_{2}, S) \Rightarrow_{*}^{μ} (q, w_{2}, α A β)$ means $S_{q_{0}} \Rightarrow_{*}^{μ} w_{1} α A β$ , thus on applying the state grammar rule (q, B) = (p, γ) will be $S_{q_{0}} \Rightarrow_{*}^{μ} w_{1} α A β = w_{1} α B β \Rightarrow w_{1} α γ β = w_{1} w$ □

Using Theorem 1 and Theorem 2, we have proved that $(q_{0}, w_{1} w_{2}, S) \Rightarrow_{*}^{μ} (q, w_{2}, α)$ if and only if $S_{q_{0}} \Rightarrow_{*}^{μ} w_{1} α$ . Now, consider w₂ = α = ɛ, then w = w₁. It gives, $(q_{0}, w, S) \Rightarrow_{*}^{μ} (q, ɛ, ɛ)$ if and only if $S_{q_{0}} \Rightarrow_{*}^{μ} w$ . String w is accepted by M_fd and G_fs with membership value μ. Hence L (M_fd) = L (G_fs)

6 Conclusion

This paper defines a novel concept of fuzzy state grammar and fuzzy deep pushdown automaton. We demonstrate increased power, in terms of erroneous string acceptance, using fuzziness in state grammar and deep pushdown automaton. Furthermore, depending upon the errors and certainty, we decide whether the string belongs to the language or not depending upon its membership value. The three main results demonstrated in this paper are: (a.) Construction of fuzzy deep pushdown automaton from fuzzy state grammar; (b.) Construction of fuzzy state grammar from fuzzy deep pushdown automaton; and (c.) If Fuzzy deep pushdown automaton M_fd is constructed from the fuzzy state grammar using the above construction method G_fs, then L (M_fd) = L (G_fs). To the best of author’s knowledge, no previous fuzzy state grammar and fuzzy deep pushdown automaton work has been reported in the literature. Future researchers might look to the real-time application of fuzzy regulated grammar in the field of biological computing.

Footnotes

Acknowledgments

Nidhi Kalra was supported under Visvesvaraya PHD Scheme fellowship by Department of Electronics and Information Technology, Ministry of Communication & IT, Government of India.

References

Dassow

and Pawn

, Regulated rewriting in formal language theory, Springer Publishing Company, 2012.

Dassow

, Grammars with regulated rewriting, Formal Languages and Applications, Studies in Fuzziness and Soft Computing 148, SpringerBerlin Heidelberg, pp. 2004, 249–273.

Meduna

, Formal Languages and Computation: Models and their applications, CRC Press, 2014.

Kumar

and Verma

A.K.

, An improved algorithm for the metamorphosis of semi-extended regular expressions to deterministic finite automata, The Computer Journal58 (2015), 448–456.

Kumar

and Verma

A.K.

, A novel algorithm for the conversion of parallel regular expressions to non-deterministic finite automata, Applied Mathematics & InformationSciences8(1) (2014), 95–105.

and Pedrycz

, Fuzzy finite automata and fuzzy regular expressions with membership values in lattice-ordered monoids, Fuzzy Sets and Systems156(1) (2005), 68–92.

Moraga

, An approach to fuzzy context-free languages, In: XIV Sanish Congress on Fuzzy Logic Technologies, Langreo-Mires, 2008, pp. 73–78.

Asveld

P.R.J.

, Controlled Fuzzy parallel rewriting in: New Trends in Formal Languages—Control, Cooeration, and Combinatorics 1218, Springer-Verlag, 1997, pp. 49–70.

Asveld

P.R.J.

, The non-self-embedding property for generalized fuzzy context-free grammars, Publicationes Mathematicae Debrecen54(Suppl 1) (1999), 553–573.

10.

Lan

, A machine accepted fuzzy context-free languages-fuzzy pushdown automata, BUSEFAL49 (1992), 67–72.

11.

Lee

E.T.

and Zadeh

L.A.

, Note on fuzzy languages, Information Sciences1(4) (1969), 421–434.

12.

Wang

and Qiu

, Computing with words via Turing machines: A formal approach, IEEE Transactions on Fuzzy System11(6) (2003), 742–753.

13.

Kasai

, An hierarchy between context-free and context-sensitive languages, Journal of Computer and System Sciences4(5) (1970), 492–508.

14.

Meduna

, Deep pushdown automata, Acta Informatica42(8-9) (2006), 541–552.

15.

Solar

and Meduna

, Deep Pushdown Transducers and State Translation Schemes, Brno University of Technology, In Proceedings of the 20th Conference STUDENT EEICT2014, pp. 264–268.

16.

Asveld

P.R.J.

, Fuzzy context-free languages Part 1: Generalized fuzzy context-free grammars, Theoretical Computer Science347(1) (2005), 167–190.

17.

Asveld

P.R.J.

, Fuzzy context-free languages Part 2: Recognition and parsing algorithms, Theoretical Computer Science347(1) (2005), 191–213.

18.

Schneider

, Lim

and Shoaff

, The utilization of fuzzy sets in the recognition of imperfect strings, Fuzzy Sets and Systems49(3) (1992), 331–337.

19.

Inui

, Shoaff

, Fausett

and Schneider

, The recognition of imperfect strings generated by fuzzy context-sensitive grammars, Fuzzy Sets and Systems62(1) (1994), 21–29.

20.

Xing

, Fuzzy pushdown automata, Fuzzy Sets and Systems158(13) (2007), 1437–1449.

21.

Bucurescu

and Pascu

, Fuzzy pushdown automata, International Journal of Computer Mathematics10(2) (1981), 109–119.

22.

Hopcroft

J.E.

, Motwani

and Ullman

J.D.

, Introduction to Automata Theory, Languages and Computation, Pearson Education, Singapore, 2000.

23.

Rosenkrantz

D.J.

, Programmed grammars and classes of formal languages, Journal of the ACM16(1) (1969), 107–131.

24.

Cremers

A.B.

and Mayer

, On matrix languages, Information and Control23(1) (1973), 86–96.

25.

Ginsburg

and Spanier

E.H.

, Control sets on grammars, Mathematical Systems Theory2(2) (1968), 159–177.

26.

Meduna

, Generalized forbidding grammars, International Journal of Computer Mathematics36(1-2) (1990), 31–38.

27.

Zemek

, One-sided random context grammars: Established results and open problems, In Proceedings of the 19th Conference STUDENT EEICT3 (2013), 222–226.

28.

Paun

, A variant of random context grammars: i-conditional grammars, Theoretical Computer Science41 (1985), 1–17Sem.

29.

Meduna

and Zemek

, One-sided random context grammars with a limited number of right random context rules, Theoretical Computer Science516 (2014), 127–132.

30.

Meduna

and Zemek

, One-sided forbidding grammars and selective substitution grammars, International Journal of Computer Mathematics89(5) (2012), 586–596.

31.

Meduna

and Zemek

, Generalized one-sided forbidding grammars, International Journal of Computer Mathematics90(2) (2013), 172–182.

32.

Cao

and Ezawa

, Nondeterministic fuzzy automata, Information Sciences191 (2012), 86–97.