An Improved Proof of the Closure Under Homomorphic Inverse of FCFL Valued in Lattice-Ordered Monoids

Abstract

We study fuzzy context-free grammars (FCFG), fuzzy context-free languages (FCFL) and fuzzy pushdown automata (FPDA) valued in lattice-ordered monoids. Inspired by the ideas of crisp cases, we get similar results, but some of them depend on commutative law. Particularly, we give two proofs of the closure under homomorphic inverse of FCFL when lattice-ordered monoids are commutative. Comparing with the classical method, we show that the improved proof is more efficient.

Supported by the National Natural Science Foundation of China under Grant 11301321, Grant 61673250, Grant 61672023.

1 Introduction

The characterization of formal languages is a very important aspect of research in the classical computation theory. For example, regular languages can be characterized by some finite automata, regular expressions and regular grammars. However, the problem of vagueness and imprecision are frequently encountered in the study of natural languages. In order to represent the imprecision of natural languages, various fuzzy languages have been proposed. By introducing the concept of fuzziness into the structure of formal grammars, the concept of fuzzy automata was introduced by Santos [22, 23] as early as in the late 1960s, and after the concept of fuzzy grammar was introduced by Lee and Zadeh [13, 14]. There are amount of work on fuzzy languages, such as the relationships between fuzzy grammars and fuzzy languages, the relations of fuzzy automata and fuzzy language, and the algebraic properties of fuzzy languages [2, 17, 18]. As a further extension, Kim et al. put forward one type of L-fuzzy grammar based on the distributive lattice and Boolean lattice, another type of L-fuzzy grammar based on lattice-ordered monoid by assigning the element of lattice to the rewriting rules of a formal grammar [11]. Gerla also studied fuzzy grammars and recursively enumerable fuzzy languages, and proved that a fuzzy language can be generated by a fuzzy grammar if and only if it is recursively enumerable [6]. As one of the generators of fuzzy languages, fuzzy grammars have been used to solve some important questions such as intelligent interface design (Senay) [25], lexical analysis, clinical monitoring (Steimann and Adlassning) [26], neural networks (Giles et al.) [19], and pattern recognition (Depalma and Yau) [4]. It is known that the context-free grammars are powerful than regular grammars, also the classical pushdown automata and finite automata [9, 24]. Therefore, fuzzy pushdown automata and fuzzy context-free grammars were discussed in [3, 12, 16, 24, 27, 28] and automata theory based on residuated lattice-valued logic has been investigated recently [21, 28]. It is shown that their many properties are similar to classical pushdown automata, context-free grammars and context-free languages. In particular, we can get a much more efficient way to prove the closure under homomorphic inverse of fuzzy context-free languages.

In this paper, fuzzy context-free languages whose codomain forms a commutative lattice-ordered monoid $\mathcal {L}$ are studied. Furthermore, we show that the homomorphic inverse of fuzzy context-free languages are also fuzzy context-free languages by two ways, and the latter is much more efficient than the former by comparison.

The rest of the paper is arranged as follows. In Sect. 2, we introduce lattice-ordered monoids and give some examples. In Sect. 3, we discuss fuzzy context-free grammars, fuzzy context-free languages and their relationships. Section 4 studies the fuzzy pushdown automata valued in a lattice-ordered monoid $\mathcal {L}$. In Sect. 5, comparing with the classical cases, we give an improved proof of the closure under homomorphic inverse of fuzzy context-free languages, which increases the efficiency of operation. Finally, some conclusions are concerned in Sect. 6.

2 Lattice-Ordered Monoids

We first introduce the definition of lattice-ordered monoid and give some examples.

Definition 2.1

Given a lattice $\mathcal {L}$, we use $\vee ,\wedge$ to represent the supremum operation and infimum operation on $\mathcal {L}$, respectively. We need $\mathcal {L}$ to have the least and largest elements in the paper, which will be denoted as 0, 1, respectively. Assume that there is a binary operation $\bullet$ (we call it multiplication) on $\mathcal {L}$ such that $(\mathcal {L},\bullet ,e)$ is a monoid with identity $e\in \mathcal {L}$.

We call $\mathcal {L}$ an po-monoid (some modification of the notion of partially ordered monoid in [5]) if it satisfies the following two conditions for any $a,b,x\in \mathcal {L}$,

• (1) $\forall a\in \mathcal {L},a\bullet 0=0\bullet a=0,$

• (2) $a\le b\Rightarrow a\bullet x\le b\bullet x$ and $x\bullet a \le x\bullet b$.

And we call $\mathcal {L}$ a lattice-ordered monoid or l-monoid if $\mathcal {L}$ is a po-monoid and it satisfies the distributive laws, i.e.,

• (3) $\forall a,b,c\in \mathcal {L},a\bullet (b\vee c)=(a\bullet b)\vee (a\bullet c)$ and $(b\vee c)\bullet a=(b\bullet a)\vee (c\bullet a)$.

Moreover, if $\mathcal {L}$ is a complete lattice, and it satisfies the following infinite distributive laws,

• (4) $a\bullet (\bigvee _{t}b_{t})=\bigvee _{t}(a\bullet b_{t})$ and $(\bigvee _{t}b_{t})\bullet a=\bigvee _{t}(b_{t}\bullet a)$,

where T is an index set, then we call $\mathcal {L}$ a quantale. If the distributive laws in (3) holds only for countable set $\{b_{t}\}_{t\in T}$ then $\mathcal {L}$ is called a countable lattice-ordered monoid.

We call the lattice-ordered monoid $(\mathcal {L},\bullet ,\vee )$ is commutative, if $a\bullet b=b\bullet a$ holds for any $a,b\in \mathcal {L}$. For a lattice-ordered monoid, we only concern the multiplication $\bullet$ and finite supremum operation $\vee$, in what follows, a lattice-ordered is denoted as $(\mathcal {L}, \bullet , \vee )$. If we deal with the subalgebra $\mathcal {L}_1$ of a lattice-ordered monoid$(\mathcal {L}, \bullet , \vee )$, it means that $\mathcal {L}_1$ is a nonempty subset of $\mathcal {L}$ and $\mathcal {L}_1$ is closed under the multiplication and finite supremum of $\mathcal {L}$. We do not concern with the infimum operation in $\mathcal {L}_1$.

The followings are discussed on the lattice-ordered monoid $\mathcal {L}$ without special instructions.

Example 2.1

• (1) Let $(\mathcal {L},\wedge ,\vee )$ be a distributive lattice, and let $\wedge =\bullet$, then $\mathcal {L}$ is a lattice-ordered monoid, and the identity of multiplication is 1.

• (2) Let $(\mathcal {L},\bullet ,\vee )$ be a lattice-ordered monoid, the identity is e. We use L(n) to denote all $n\times n$ matrices with values in $\mathcal {L}$. The multiplication, denote as $\circ$, is defined as $Sup-\bullet$ composition; and $\vee$ is the pointwise-$\vee$. That is, for two $n \times n$ matrices, $A=(a_{ij}),B=(b_{ij}),$ with values in $\mathcal {L}$, let $A\circ B=C=(c_{ij}),$ then $c_{ij}=\vee _{k=1}^n(a_{ik}\bullet b_{kj})$ and let $A\vee B=D=(d_{ij}), d_{ij}=a_{ij}\vee b_{ij}$. Then $(L(n),\circ ,\vee )$ is also a lattice-ordered monoid, the identity is the diagonal-matrix $E=diag(e,\cdots ,e)$, with e as the diagonal element. In general, the multiplication on L(n) is not commutative, even if the multiplication on $\mathcal {L}$ is commutative.

• (3) Let $\bullet$ be any uninorm on [0,1]. If $0\bullet 1=0$, then$([0,1],\bullet ,\vee )$ is a commutative lattice-ordered monoid. In particular, if $\bullet$ is a t-norm on [0,1], then $0\bullet 1=0$, then $([0,1],\bullet ,\vee )$ is a commutative lattice-ordered monoid with identity $e=1$.

• (4) Complete residuated lattices are special kinds of quantales, where its multiplication is commutative and the identity is the same as the largest element.

3 Fuzzy Grammars

In this section, we study fuzzy context-free grammars, fuzzy context-free languages and their relationships.

Definition 3.1

Fuzzy grammar is a four tuple $G=(N,T,P,S)$, where N is a finite nonterminal alphabet and its elements are called variables; T is a finite terminal alphabet, $N\cap T=\emptyset$; $S\in N$ is a start symbol; P is a finite alphabet of fuzzy productions $u\rightarrow ^{\rho }v$, where $u\in (N\bigcup T)^{*}N(N\bigcup T)^{*}$, $v\in (N\bigcup T)^{*}$, and $\rho \in \mathcal {L}-\{0\}$ represents the membership value of rewriting rule $u\rightarrow v$. We suppose S only appears in the left of fuzzy production $u\rightarrow v$.

For $u_{1},\cdots ,u_{n}\in (N\bigcup T)^{*}$, if $u_{1}\Rightarrow ^{\rho _{1}}u_{2}\Rightarrow ^{\rho _{2}}\cdots \Rightarrow ^{\rho _{n-1}}u_{n}$, then $u_{n}$ called the derivation chain from $u_{1}$, denoted as $u_{1}\Rightarrow ^{\rho }_{*}u_{n}$, where $\rho =\rho _{1}\bullet \rho _{2}\bullet \cdots \bullet \rho _{n-1}$.

Definition 3.2

The fuzzy language $L(G):T^{*}\rightarrow \mathcal {L}$ generated by fuzzy grammar G is defined as, for any $\theta \in T^{*}$,

$$ L(G)(\theta )=\vee \{\rho |S\Rightarrow _{*}^{\rho }\theta \}. $$

Fuzzy grammar, also called type 0 grammar or fuzzy phrase grammar, it is further classified as follows.

Suppose that $G=(N,T,P,S)$ is a fuzzy grammar, then

• (1) G is called fuzzy context-sensitive grammar (FCSG) or type 1 grammar, if for any $u\rightarrow ^{\rho }v\in P$, there is $|u|\le |v|$. And L(G) is called fuzzy context-sensitive language (FCSL).

• (2) G is called fuzzy context-free grammar (FCFG) or type 2 grammar, if for any $u\rightarrow ^{\rho }v\in P$, there is $|u|\le |v|$ and $u\in N$. And L(G) is called fuzzy context-free language (FCFL).

• (3) G is called fuzzy regular grammar (FRG) or type 3 grammar, if for any $u\rightarrow ^{\rho }v\in P$, there is $u\in N$ and $v\in TB$, $B\in N\cup \{\varepsilon \}$, or $u=S,v=\varepsilon$. And L(G) is called fuzzy context-free language (FRL).

In the paper, we only concern with the fuzzy context-free grammar.

Definition 3.3

Suppose that $G=(N,T,P,S)$ is a fuzzy context-free grammar, then G is called fuzzy Chomsky normal form (FCNF) if for any production formula of G they have the form:

$$\begin{aligned} A\rightarrow ^{\rho }BC \text { or } A\rightarrow ^{\rho }a \text { or } S\rightarrow ^{\rho }\varepsilon , \end{aligned}$$

where $A,B,C\in N,a\in T,\rho \in \mathcal {L}-\{0\}$.

Theorem 4.1. For any fuzzy context-free grammar, there is an equivalent Chomsky normal form.

4 Fuzzy Pushdown Automata

Now, we give the fuzzy pushdown automata valued in a lattice-ordered monoid $\mathcal {L}$.

Definition 4.1

Fuzzy pushdown automata (FPDA) is a seven tuple $M=(Q,\varSigma ,$ $\varGamma ,\delta ,q_{0},Z_{0},F)$, where $Q,\varSigma ,\varGamma$ are nonempty finite sets, and they represent state sets, input alphabet, stack alphabet, respectively. $q_{0}\in Q ,Z_{0}\in \varGamma$ represent initial state and start symbol. $F:Q\rightarrow \ \mathcal {L}$ is a fuzzy final state, $\delta :Q\times (\varSigma \cup \{\varepsilon \})\times \varGamma \rightarrow F(Q\times \varGamma ^{*})$ which image is a finite fuzzy subset of $Q\times \varGamma ^{*}$ is called fuzzy transition function.

For any $p, q\in Q, \sigma \in \varSigma , Z\in \varGamma , \gamma \in \varGamma ^{*}, \delta (q,\sigma ,Z)(p,\gamma )$ means the possible degree that automata can enter next state p and the top stack letter Z transfer to $\gamma$ when current state is q, the top stack letter is Z and the input symbol is $\sigma$. Similarly, $\delta (q,\varepsilon ,Z)(p,\gamma )$ means the possible degree that the automata turn to the next state p and the top stack letter Z transfer to $\gamma$ when current state is q, the top stack letter is Z and the input symbol is empty string. What’s more, for any $(q,w,\gamma )\in Q\times \varSigma ^{*}\times \varGamma ^{*}$, it is called a instantaneous description of M and ID for short, it means that M is on the current state q, w is the untreated input string and M is focusing on the first character of w, the string in the stack is $\gamma$.

For $\alpha , \beta \in \varGamma ^{*}$, $\beta$ is the tail of $\alpha$ if there exists $\gamma \in \varGamma ^{*}$ such that $\alpha =\gamma \beta$, denoted $\beta \le \alpha$ and $\gamma =\alpha \setminus \beta$, $head(\beta )$ is the first character of $\beta$. Then we give the extension $\nabla$ of $\delta$ as follows.

Definition 4.2

Given a fuzzy pushdown automata $M=(Q,\varSigma ,\varGamma ,\delta ,q_{0},Z_{0},F)$, we define the fuzzy relation $\nabla$ in $Q\times \varSigma ^{*}\times \varGamma ^{*}$ as,

$$\begin{aligned} \nabla ((p,w,\beta ),(q,v,\alpha ))= \left\{ \begin{array}{ll} \delta (p,\varepsilon ,head(\beta ))(q,\alpha \setminus tail(\beta )), &{} v=w,tail(\beta )\le \alpha ,\\ \delta (p,head(w),head(\beta )(q,\alpha \setminus tail(\beta )), &{} v=tail(w),tail(\beta )\le \alpha ,\\ 0, &{} otherwise. \end{array} \right. \end{aligned}$$

$\nabla ^{*}$ is defined as the reflexive and transitive closure of $\nabla$. The reflexive and transitive closure of fuzzy relation R in set Q is defined as $R^{*}=I\cup R\cup R\circ R\cup \cdots \cup R^{n}\cup \cdots$, where $\circ$ is $Sup-\bullet$ composition of fuzzy relations.

Definition 4.3

Given a fuzzy pushdown automata $M=(Q,\varSigma ,\varGamma ,\delta ,q_{0},Z_{0},F)$, for all $\theta \in \varSigma ^{*}$,

(1) The fuzzy language accepted by M by final state is defined as,

$$\begin{aligned} L(M)(\theta )=\bigvee _{q\in Q,\gamma \in \varGamma ^{*}}[\nabla ^{*}((q_{0},\theta ,Z_{0}),(q,\varepsilon ,\gamma ))\bullet F(q)]. \end{aligned}$$

(2) The fuzzy language accepted by M by empty stack is defined as,

$$\begin{aligned} N(M)(\theta )=\bigvee _{q\in Q}\nabla ^{*}((q_{0},\theta ,Z_{0}),(q,\varepsilon ,\varepsilon )). \end{aligned}$$

Theorem 4.1

For an FPDA that accepts a fuzzy language L by empty stack, there exists another FPDA that accepts L by final states. And the vise versa.

Corollary 4.1

The fuzzy final states can be taken as crisp states when the FPDA accept fuzzy language by the final state.

Theorem 4.2

For a fuzzy language, it can be accepted by an FPDA iff the fuzzy language is FCFL.

5 The Properties of Fuzzy Context-Free Language

this section, we investigate some properties of fuzzy context-free languages, and except the closure under homomorphic inverse, the proofs of other conclusions are similar to the classical conditions, so we don’t give their proofs in this paper.

Definition 5.1

Let f, g be any fuzzy context-free language on $\varSigma ^{*}$ that valued in a lattice-ordered monoid $\mathcal {L}$, and $a\in \mathcal {L},\theta \in \varSigma ^{*}$, then we defined the operations as follows:

• (1) The scalar product of a and f, denoted af and fa, is defined as, $(af)(\theta )=a\bullet f(\theta )$ and $(fa)(\theta )=f(\theta )\bullet a$.

• (2) The union of $f_{1}$ and $f_{2}$, denoted $f_{1}\cup f_{2}$, is defined as, $(f_{1}\cup f_{2})(\theta )=f_{1}(\theta )\vee f_{2}(\theta )$.

• (3) The concatenation of $f_{1}$ and $f_{2}$, denoted $f_{1}f_{2}$, is defined as, $(f_{1}f_{2})(\theta )=\bigvee _{\theta _{1}\theta _{2}=\theta }[f_{1}(\theta _{1})\bullet f_{2}(\theta _{2})]$. And then the concatenation operation satisfies the associative laws.

Definition 5.2

Let $\varSigma ,\varDelta$ be finite nonempty character sets, $\phi :\varSigma \rightarrow F(\varDelta ^{*})$ is a mapping, and $\phi$ is called fuzzy context-free substitution if $\phi (\sigma )$ is a fuzzy context-free language of $\varDelta$ for any $\sigma \in \varSigma$.

Given a mapping $\phi :\varSigma \rightarrow F(\varDelta ^{*})$, then $\phi$ can be extended on $\varSigma ^{*}$ by the way as follows,

• (1) $\phi (\varepsilon )=\{\frac{1}{\varepsilon }\}$;

• (2) $\forall \theta \in \varSigma ^{*}, \forall \sigma \in \varSigma , \phi (\theta \sigma )=\phi (\theta )\phi (\sigma )$.

Then we extend $\phi$ on $F(\varSigma ^{*})$, denoted as, $\phi :F(\varSigma ^{*})\rightarrow F(\varDelta ^{*})$, and $\forall h\in F(\varSigma ^{*}),\forall \omega \in \varDelta ^{*}$,

$$\begin{aligned} \phi (h)(\omega )=\bigvee _{\theta \in \varSigma ^{*}}[h(\theta )\bullet \phi (\theta )(\omega )]. \end{aligned}$$

Definition 5.3

A mapping $\phi :\varSigma \rightarrow F(\varDelta ^{*})$ is called fuzzy homomorphism, if for any $\sigma \in \varSigma$, there exists unique $w\in \varSigma ^{*}, a\in \mathcal {L}-\{0\}$ such that $\phi (\sigma )=\frac{a}{w}$. For the above mapping $\phi$ and $\sigma \in \varSigma$, we can define two mappings $\phi _{1}:\varSigma \rightarrow \varDelta ^{*}$ and $\phi _{2}:\varSigma \rightarrow \mathcal {L}$ as, $\phi _{1}(\sigma )=w$, $\phi _{2}(\sigma )=a$, respectively. Then $\phi _{1}$ is the usual homomorphism, therefore, $\forall \sigma \in \varSigma ,\phi (\sigma )=\frac{\phi _{2}(\sigma )}{\phi _{1}(\sigma )}$.

Then we can extend $\phi _{1}$ and $\phi _{2}$ on $\varSigma ^{*}$ as, $\forall \theta =\sigma _{1}\cdots \sigma _{k}\in \varSigma ^{*}$, $\phi _{1}(\sigma _{1}\cdots \sigma _{k})=\phi _{1}(\sigma _{1})\cdots \phi _{1}(\sigma _{k})$, and $\phi _{2}(\sigma _{1}\cdots \sigma _{k})=\phi _{2}(\sigma _{1})\bullet \cdots \bullet \phi _{2}(\sigma _{k})$. Besides, we declare that $\phi _{1}(\varepsilon )=\varepsilon$, $\phi _{2}(\varepsilon )=e$.

Thus, we can extend $\phi$ on $F(\varSigma ^{*})$ as,

$$\begin{aligned} \forall g\in F(\varSigma ^{*}), \quad \forall \omega \in \varDelta ^{*}, \quad \phi (g)(\omega )=\vee \{g(\theta )\bullet \phi _{2}(\theta )|\phi _{1}(\theta )=\omega \}, \end{aligned}$$

at the same time, we define the inverse mapping $\phi ^{-1}:F(\varDelta ^{*})\rightarrow F(\varSigma ^{*})$ as,

$$\begin{aligned} \forall h\in F(\varDelta ^{*}),\quad \forall \theta \in \varSigma ^{*}, \quad \phi ^{-1}(h)(\theta )=h(\phi _{1}(\theta ))\bullet \phi _{2}(\theta ). \end{aligned}$$

Theorem 5.1

Any FCFL is still an FCFL under the fuzzy context-freesubstitution.

By the extensive definition of fuzzy homomorphism, we know that fuzzy context-free homomorphism is a special type of fuzzy context-free substitution, so we can get the following conclusion.

Corollary 5.1

Suppose that $\phi :\varSigma \rightarrow F(\varDelta ^{*})$ is a fuzzy homomorphism, then $\phi (f)$ is an FCFL on $\varDelta$ if f is an FCFL on $\varSigma$.

That is to say, fuzzy context-free languages are closed under the fuzzy homomorphism, now we consider the fuzzy homomorphic inverse of fuzzy context-free languages in Definition 5.2. Suppose that f is a fuzzy context-free language on $\varDelta$, $\phi :\varSigma \rightarrow F(\varDelta ^{*})$ is a fuzzy homomorphism, then f can be described by a fuzzy context-free grammar and accepted by a fuzzy pushdown automata. If $\phi ^{-1}(f)$ is a fuzzy context-free language, there must be a fuzzy context-free grammar and a fuzzy pushdown automata corresponding to it. Here we only consider designing a fuzzy pushdown automata to accept it. Assume that $M_{2}$ is a fuzzy pushdown automata that accepts f. We need construct a fuzzy pushdown automata $M_{1}$ which can simulate the processing of $M_{2}$ to $\phi _{1}(a)$ when $M_{1}$ reads character a. But, we can’t ignore the degree of the processing, that is $\phi _{2}(a)$. For one thing, we need to store $\phi _{1}(a)$ in the finite controller of $M_{1}$, and the degree of this process is $\phi _{2}(a)$. For another thing, $\phi _{1}(a)$ is a string, we need to simulate the process of $M_{2}$ to $\phi _{1}(a)$. Now we give two ways to complete the process, and the second solution is an improved way.

• (1) We can use an empty move of $M_{1}$ to simulate the process of $M_{2}$ to each character of $\phi _{1}(a)$, and $M_{2}$ running $|\phi _{1}(a)|$ steps when it finished processing $\phi _{1}(a)$. This way is similar to the process of classical case, but what we should concern about is just the possible degree each transition of $M_{2}$.

• (2) We can use an empty move of $M_{1}$ to simulate the process of $M_{2}$ to the whole string $\phi _{1}(a)$, then let $M_{1}$ remember the state and stack letter, which are M turns to after it finished processing $\phi _{1}(a)$. In the process, the possible transition degree of $M_{1}$ is just the possible degree that $M_{2}$ processed string $\phi _{1}(a)$.

Remark 5.1

From the definition of $\nabla ^{*}$, it is clearly that if $M=(Q,\varSigma ,\varGamma ,\delta ,q_{0},Z_{0},$ F) is a fuzzy pushdown automata, $p, q\in Q, x, y\in \varSigma ^{*}, \alpha , \beta \in \varGamma ^{*}$, then $\nabla ^{*}((q,x,\alpha )$, $(p,y,\beta ))=\nabla ^{*}((q,x\omega ,\alpha ),(p,y\omega ,\beta ))$ holds for any $\omega \in \varSigma ^{*}$.

We will frequently use the fact to prove the following theorem.

Theorem 5.2

If $\mathcal {L}$ is commutative, then the homomorphic inverse of FCFL is FCFL.

Proof

I.   Let f be a fuzzy context-free language of $\varDelta$, $\phi :\varSigma \rightarrow F(\varDelta ^{*})$ is a fuzzy homomorphism. Then there is a fuzzy pushdown automata $M_{2}=(Q_{2},\varDelta ,\varGamma ,\delta _{2},q_{0}$, $Z_{0},\{q_{f}\})$ which accepts f, that is, for any $\theta$ in $\varDelta ^{*}$, $f(\theta )=L(M_{2})(\theta )=\bigvee _{\gamma \in \varGamma ^{*}}\nabla _{2}^{*}$ $((q_{0},\theta ,Z_{0}),(q_{f},\varepsilon ,\gamma ))$. Now we construct a fuzzy pushdown automata $M_{1}=(Q_{1},\varDelta ,\varGamma ,\delta _{1},[q_{0},\varepsilon ],Z_{0},[q_{f},\varepsilon ])$ as,

• (1) $Q_{1}=\{[q,x]|\forall a\in \varSigma \bigcup \{\varepsilon \},x$ is a suffix of $\phi _{1}(a)\}$, where the number of the suffix of $\phi _{1}(a)$ is finite, and $Q_{2}$ is a finite set, so $Q_{1}$ is finite.

• (2) $\forall q\in Q_{2}, a\in \varSigma \bigcup \{\varepsilon \}, Z \in \varGamma , \delta _{1}([q,\varepsilon ],a,Z)([q,\phi _{1}(a)],Z)=\phi _{2}(a)$.

• (3) $\forall q ,p \in Q_{2}, u\in \varSigma \cup \{\varepsilon \}, \gamma \in \varGamma ^{*}, \delta _{1}([q,ux],\varepsilon ,Z)([p,x],\gamma )= \delta _{2}(q,u,Z)(p,\gamma )$, and for other cases, $\delta _{1}=0$.

Therefore, if $\theta =\varepsilon$, then

$$\begin{aligned} L(M_{1})(\varepsilon )&=\bigvee _{\gamma \in \varGamma ^{*}}\nabla _{1}^{*}(([q_{0},\varepsilon ],\varepsilon ,Z_{0}),([q_{f},\varepsilon ],\varepsilon ,\gamma ))\\&=\bigvee _{\gamma \in \varGamma ^{*}}\nabla _{1}(([q_{0},\varepsilon ],\varepsilon ,Z_{0}),([q_{0},\phi _{1}(\varepsilon )],\varepsilon ,Z_{0}))\bullet \nabla _{1}(([q_{0},\phi _{1}(\varepsilon )],\varepsilon ,Z_{0}),([q_{f},\varepsilon ],\varepsilon ,\gamma ))\\&=\bigvee _{\gamma \in \varGamma ^{*}}\delta _{1}([q_{0},\varepsilon ],\varepsilon ,Z_{0})([q_{0},\phi _{1}(\varepsilon )],Z_{0})\bullet \delta _{1}([q_{0},\phi _{1}(\varepsilon )],\varepsilon ,Z_{0})([q_{f},\varepsilon ],\gamma )\\&=\bigvee _{\gamma \in \varGamma ^{*}}\nabla _{2}^{*}((q_{0},\phi _{1}(\varepsilon ),Z_{0}),(q_{f},\varepsilon ,\gamma ))\bullet \phi _{2}(\varepsilon )\\&=f(\phi _{1}(\varepsilon ))\bullet \phi _{2}(\varepsilon )\\&=\phi ^{-1}(f)(\varepsilon ). \end{aligned}$$

Note that for any $\theta \in \varSigma ^{+}$, let $\theta =a_{1}\cdots a_{n}$, $a_{i}\in \varSigma$, $\phi _{1}(a_{i})=b_{i1}\cdots b_{im}$, $i=1,2,...,n,|\phi _{1}(a_{i})|=m$, then $\phi _{1}(\theta )=\phi _{1}(a_{1})\cdots \phi _{1}(a_{n})$, $\phi _{2}(\theta )=\phi _{2}(a_{1})\bullet \cdots \bullet \phi _{2}(a_{n})$, therefore,

$$\begin{aligned} L(M_{1})(\theta )&=\bigvee _{\gamma \in \varGamma ^{*}}\nabla _{1}^{*}(([q_{0},\varepsilon ],\theta ,Z_{0}),([q_{f},\varepsilon ],\varepsilon ,\gamma ))\\&=\bigvee _{\gamma _{i}\in \varGamma ^{*},q_{i}\in Q_{2}}[\nabla _{1}(([q_{0},\varepsilon ],a_{1}\cdots a_{n},Z_{0}),([q_{0},\phi _{1}(a_{1})],a_{2}\cdots a_{n},Z_{0}))\\&\bullet \nabla _{1}(([q_{0},\phi _{1}(a_{1})],\varepsilon a_{2}\cdots a_{n},Z_{0}),([q_{1},\varepsilon ],a_{2}\cdots a_{n},\gamma _{1}))]\\&\bullet [\nabla _{1}(([q_{1},\varepsilon ],a_{2}\cdots a_{n},\gamma _{1}),([q_{1},\phi _{1}(a_{2})],a_{3}\cdots a_{n},\gamma _{1}))\\&\bullet \nabla _{1}(([q_{1},\phi _{1}(a_{2})],\varepsilon a_{3}\cdots a_{n},\gamma _{1}),([q_{2},\varepsilon ],a_{3}\cdots a_{n},\gamma _{2}))]\bullet \cdots \\ \end{aligned}$$

$$\begin{aligned}&\bullet [\nabla _{1}(([q_{n-1},\varepsilon ],a_{n},\gamma _{n-1}),([q_{n-1},\phi _{1}(a_{n})],\varepsilon ,\gamma _{n-1}))\\&\bullet \nabla _{1}(([q_{n-1},\phi _{1}(a_{n})],\varepsilon ,\gamma _{n-1}),([q_{f},\varepsilon ],\varepsilon ,\gamma ))]\\&=\bigvee _{\gamma ,\gamma _{i}\in \varGamma ^{*},q_{i}\in Q_{2}}[\delta _{1}(([q_{0},\varepsilon ],a_{1},Z_{0})([q_{0},\phi _{1}(a_{1})],Z_{0})\\&\bullet \delta _{1}([q_{0},b_{11}\cdots b_{1m}],\varepsilon ,Z_{0})([q_{1},\varepsilon ],\gamma _{1})] \bullet \cdots \\&\bullet [\delta _{1}([q_{n-1},\varepsilon ],a_{n},\gamma _{n-1})([q_{n-1},\phi _{1}(a_{n})],\gamma _{n-1})\\&\bullet \delta _{1}([q_{n-1},b_{n1}\cdots b_{nm}],\varepsilon ,\gamma _{n-1})([q_{f},\varepsilon ],\gamma )]\\&=\bigvee _{\gamma ,\gamma _{i}\in \varGamma ^{*},q_{i},q_{ij}\in Q_{2}}[\phi _{2}(a_{1})\bullet \delta _{1}([q_{0},b_{11}\cdots b_{1m}],\varepsilon ,Z_{0})([q_{01},b_{12}\cdots b_{1m}],\gamma _{01})\\&\bullet \delta _{1}([q_{01},b_{12}\cdots b_{1m}],\varepsilon ,\gamma _{01})([q_{02},b_{13}\cdots b_{1m}],\gamma _{02})\bullet \cdots \\&\bullet \delta _{1}([q_{0(m-1)},b_{1m}],\varepsilon ,\gamma _{0(m-1)})([q_{1},\varepsilon ],\gamma _{1})]\\&\bullet \cdots \bullet \\&\phi _{2}(a_{n})\bullet [\delta _{1}([q_{n-1},b_{n1}\cdots b_{nm}],\varepsilon ,\gamma _{(n-1)})([q_{(n-1),1},b_{n2}\cdots b_{nm}],\gamma _{(n-1),1})\\&\bullet \delta _{1}([q_{(n-1),1},b_{n2}\cdots b_{nm}],\varepsilon ,\gamma _{(n-1),1})([q_{(n-1),2},b_{n3}\cdots b_{nm}],\gamma _{(n-1),2})\bullet \cdots \\&\bullet \delta _{1}([q_{(n-1)(m-1)},b_{nm}],\varepsilon ,\gamma _{(n-1)(m-1)})([q_{f},\varepsilon ],\gamma )]\\&=\bigvee _{\gamma ,\gamma _{i}\in \varGamma ^{*},q_{i},q_{ij}\in Q_{2}}[\delta _{2}(q_{0},b_{11},Z_{0})(q_{01},\gamma _{01})\bullet \delta _{2}(q_{01},b_{12},\gamma _{01})(q_{02},\gamma _{02})\bullet \cdots \\&\bullet \delta _{2}(q_{0,(m-1)},b_{1m},\gamma _{0,(m-1)})(q_{1},\gamma _{1})]\\&\bullet \cdots \bullet \\&[\delta _{2}(q_{n-1},b_{n1},\gamma _{n-1})(q_{(n-1),1},\gamma _{(n-1),1})\bullet \delta _{2}(q_{(n-1),1},b_{n2},\gamma _{(n-1),1})(q_{(n-1),2},\gamma _{(n-1),2})\bullet \cdots \\&\bullet \delta _{2}(q_{(n-1)(m-1)},b_{nm},\gamma _{(n-1)(m-1)})(q_{f},\gamma )]\\&\bullet [\phi _{2}(a_{1})\bullet \cdots \bullet \phi _{2}(a_{n})]\\&=\bigvee _{\gamma ,\gamma _{i}\in \varGamma ^{*},q_{i}\in Q_{2}}[\nabla _{2}^{*}((q_{0},b_{11}\cdots b_{1m},Z_{0}),(q_{1},\varepsilon ,\gamma _{1}))]\\&\bullet [\nabla _{2}^{*}((q_{1},b_{21}\cdots b_{2m},\gamma _{10}),(q_{2},\varepsilon ,\gamma _{2}))]\bullet \cdots \\&\bullet [\nabla _{2}^{*}((q_{n-1},b_{n1}\cdots b_{nm},\gamma _{n-1}),(q_{f},\varepsilon ,\gamma ))]\\&\bullet [\phi _{2}(a_{1})\bullet \cdots \bullet \phi _{2}(a_{n})]\\&=\bigvee _{\gamma ,\gamma _{i}\in \varGamma ^{*},q_{i}\in Q_{2}}[\nabla _{2}^{*}((q_{0},\phi _{1}(a_{1}),Z_{0}),(q_{1},\varepsilon ,\gamma _{1}))\\&\bullet \nabla _{2}^{*}((q_{1},\phi _{1}(a_{2}),\gamma _{1}),(q_{2},\varepsilon ,\gamma _{2}))\bullet \cdots \\&\bullet \nabla _{2}^{*}((q_{n-1},\phi _{1}(a_{n}),\gamma _{n-1}),(q_{f},\varepsilon ,\gamma ))]\\&\bullet [\phi _{2}(a_{1})\bullet \cdots \bullet \phi _{2}(a_{n})]\\&=\bigvee _{\gamma ,\gamma _{i}\in \varGamma ^{*},q_{i}\in Q_{2}}[\nabla _{2}^{*}((q_{0},\phi _{1}(a_{1})\phi _{1}(a_{2})\cdots \phi _{1}(a_{n}),Z_{0}),(q_{1},\varepsilon \phi _{1}(a_{2})\cdots \phi _{1}(a_{n}),\gamma _{1}))\\&\bullet \nabla _{2}^{*}((q_{1},\phi _{1}(a_{2})\phi _{1}(a_{3})\cdots \phi _{1}(a_{n}),\gamma _{1}),(q_{2},\varepsilon \phi _{1}(a_{3})\cdots \phi _{1}(a_{n}),\gamma _{2}))\bullet \cdots \\&\bullet \nabla _{2}^{*}((q_{n-1},\phi _{1}(a_{n}),\gamma _{n-1}),(q_{f},\varepsilon ,\gamma ))]\bullet \phi _{2}(\theta )\\&=\bigvee _{\gamma \in \varGamma ^{*}}[\nabla _{2}^{*}((q_{0},\phi _{1}(a_{1})\cdots \phi _{1}(a_{n}),Z_{0}),(q_{f},\varepsilon ,\gamma ))] \bullet \phi _{2}(\theta )\\&=f(\phi _{1}(\theta ))\bullet \phi _{2}(\theta )\\&=\phi ^{-1}(f)(\theta ). \end{aligned}$$

Thus, $L(M_{1})=\phi ^{-1}(f)$.

Proof

II.   Let f be a fuzzy context-free language of $\varDelta$, $\phi :\varSigma \rightarrow F(\varDelta ^{*})$ is a fuzzy homomorphism. Then there is a fuzzy pushdown automata $M_{2}=(Q_{2},\varDelta ,\varGamma ,\delta _{2},q_{0}$, $Z_{0},\{q_{f}\})$ which accepts f. Now we construct a fuzzy pushdown automata $M_{1}=(Q_{1},\varDelta ,\varGamma ,\delta _{1}$, $[q_{0},\varepsilon ],Z_{0},[q_{f},\varepsilon ])$ as,

• (1) $Q_{1}=\{[q,x]|\forall a\in \varSigma \bigcup \{\varepsilon \},x=\phi _{1}(a)\}$, where the number of $\phi _{1}(a)$ is finite, and $Q_{2}$ is a finite set, so $Q_{1}$ is finite.

• (2) $\forall q\in Q_{2}, a\in \varSigma \bigcup \{\varepsilon \}, Z \in \varGamma , \delta _{1}([q,\varepsilon ],a,Z)([q,\phi _{1}(a)],Z)=\phi _{2}(a)$,

• (3) $\forall q, p \in Q_{2}, \gamma \in \varGamma ^{*}, \delta _{1}([q,\phi _{1}(a)],\varepsilon ,Z)([p,\varepsilon ],\gamma )= \nabla _{2}^{*}((q,\phi _{1}(a),Z),(p,\varepsilon ,\gamma ))$, and for other cases, $\delta _{1}=0$.

Now we prove that $L(M_{1})=\phi ^{-1}(f)$. First, if $\theta =\varepsilon$, then

$$\begin{aligned} L(M_{1})(\varepsilon )&=\bigvee _{\gamma \in \varGamma ^{*}}\nabla _{1}^{*}(([q_{0},\varepsilon ],\varepsilon ,Z_{0}),([q_{f},\varepsilon ],\varepsilon ,\gamma ))\\&=\bigvee _{\gamma \in \varGamma ^{*}}\nabla _{1}(([q_{0},\varepsilon ],\varepsilon ,Z_{0}),([q_{0},\phi _{1}(\varepsilon )],\varepsilon ,Z_{0}))\bullet \nabla _{1}(([q_{0},\phi _{1}(\varepsilon )],\varepsilon ,Z_{0}),([q_{f},\varepsilon ],\varepsilon ,\gamma ))\\&=\bigvee _{\gamma \in \varGamma ^{*}}\nabla _{2}^{*}((q_{0},\phi _{1}(\varepsilon ),Z_{0}),(q_{f},\varepsilon ,\gamma ))\bullet \phi _{2}(\varepsilon )\\&=f(\phi _{1}(\varepsilon ))\bullet \phi _{2}(\varepsilon )\\&=\phi ^{-1}(f)(\varepsilon ). \end{aligned}$$

Note that for any $\theta \in \varSigma ^{+}$, let $\theta =a_{1}\cdots a_{n}$, $a_{i}\in \varSigma ,\ i=1,2,...,n$, $\phi _{1}(\theta )=\phi _{1}(a_{1})\cdots \phi _{1}(a_{n})$, $\phi _{2}(\theta )=\phi _{2}(a_{1})\bullet \cdots \bullet \phi _{2}(a_{n})$, then

$$\begin{aligned} L(M_{1})(\theta )&=\bigvee _{\gamma \in \varGamma ^{*}}\nabla _{1}^{*}(([q_{0},\varepsilon ],\theta ,Z_{0}),([q_{f},\varepsilon ],\varepsilon ,\gamma ))\\&=\bigvee _{\gamma _{i}\in \varGamma ^{*},q_{i}\in Q_{2}}[\nabla _{1}(([q_{0},\varepsilon ],a_{1}\cdots a_{n},Z_{0}),([q_{0},\phi _{1}(a_{1})],a_{2}\cdots a_{n},Z_{0}))\\&\bullet \nabla _{1}(([q_{0},\phi _{1}(a_{1})],\varepsilon a_{2}\cdots a_{n},Z_{0}),([q_{1},\varepsilon ],a_{2}\cdots a_{n},\gamma _{1}))]\\&\bullet [\nabla _{1}(([q_{1},\varepsilon ],a_{2}\cdots a_{n},\gamma _{1}),([q_{1},\phi _{1}(a_{2})],a_{3}\cdots a_{n},\gamma _{1}))\\&\bullet \nabla _{1}(([q_{1},\phi _{1}(a_{2})],\varepsilon a_{3}\cdots a_{n},\gamma _{1}),([q_{2},\varepsilon ],a_{3}\cdots a_{n},\gamma _{2}))]\bullet \cdots \\&\bullet [\nabla _{1}(([q_{n-1},\varepsilon ],a_{n},\gamma _{n-1}),([q_{n-1},\phi _{1}(a_{n})],\varepsilon ,\gamma _{n-1}))\\&\bullet \nabla _{1}(([q_{n-1},\phi _{1}(a_{n})],\varepsilon ,\gamma _{n-1}),([q_{f},\varepsilon ],\varepsilon ,\gamma ))]\\&=\bigvee _{\gamma ,\gamma _{i}\in \varGamma ^{*},q_{i}\in Q_{2}}[\delta _{1}([q_{0},\varepsilon ],a_{1},Z_{0})([q_{0},\phi _{1}(a_{1})],Z_{0})\\&\bullet \delta _{1}([q_{0},\phi _{1}(a_{1})],\varepsilon ,Z_{0})([q_{1},\varepsilon ],\gamma _{1})]\\&\bullet [\delta _{1}([q_{1},\varepsilon ],a_{2},\gamma _{1})([q_{1},\phi _{1}(a_{2})],\gamma _{1})\\&\bullet \delta _{1}([q_{1},\phi _{1}(a_{2})],\varepsilon ,\gamma _{1})([q_{2},\varepsilon ],\gamma _{2})]\bullet \cdots \\ \end{aligned}$$

$$\begin{aligned}&\bullet [\delta _{1}([q_{n-1},\varepsilon ],a_{n},\gamma _{n-1})([q_{n-1},\phi _{1}(a_{n})],\gamma _{n-1})\\&\bullet \delta _{1}([q_{n-1},\phi _{1}(a_{n})],\varepsilon ,\gamma _{n-1})([q_{f},\varepsilon ],\gamma )]\\&=\bigvee _{\gamma ,\gamma _{i}\in \varGamma ^{*},q_{i}\in Q_{2}}[\nabla _{2}^{*}((q_{0},\phi _{1}(a_{1}),Z_{0}),(q_{1},\varepsilon ,\gamma _{1}))\\&\bullet \nabla _{2}^{*}((q_{1},\phi _{1}(a_{2}),\gamma _{1}),(q_{2},\varepsilon ,\gamma _{2}))\bullet \cdots \\&\bullet \nabla _{2}^{*}((q_{n-1},\phi _{1}(a_{n}),\gamma _{n-1}),(q_{f},\varepsilon ,\gamma ))]\\&\bullet [\phi _{2}(a_{1})\bullet \cdots \bullet \phi _{2}(a_{n})]\\&=\bigvee _{\gamma ,\gamma _{i}\in \varGamma ^{*},q_{i}\in Q_{2}}[\nabla _{2}^{*}((q_{0},\phi _{1}(a_{1})\phi _{1}(a_{2})\cdots \phi _{1}(a_{n}),Z_{0}),(q_{1},\varepsilon \phi _{1}(a_{2})\cdots \phi _{1}(a_{n}),\gamma _{1}))\\&\bullet \nabla _{2}^{*}((q_{1},\phi _{1}(a_{2})\phi _{1}(a_{3})\cdots \phi _{1}(a_{n}),\gamma _{1}),(q_{2},\varepsilon \phi _{1}(a_{3})\cdots \phi _{1}(a_{n}),\gamma _{2}))\bullet \cdots \\&\bullet \nabla _{2}^{*}((q_{n-1},\phi _{1}(a_{n}),\gamma _{n-1}),(q_{f},\varepsilon ,\gamma ))]\bullet \phi _{2}(\theta )\\&=\bigvee _{\gamma \in \varGamma ^{*}}[\nabla _{2}^{*}((q_{0},\phi _{1}(a_{1})\cdots \phi _{1}(a_{n}),Z_{0}),(q_{f},\varepsilon ,\gamma ))] \bullet \phi _{2}(\theta )\\&=f(\phi _{1}(\theta ))\bullet \phi _{2}(\theta )\\&=\phi ^{-1}(f)(\theta ). \end{aligned}$$

Thus, $L(M_{1})=\phi ^{-1}(f)$.

Clearly, the second solution is much more efficient than the first one. Let $|Q_{2}|,|\varSigma |$ represent the number of their elements, respectively. For any $a_{i}\in \varSigma ,\phi _{1}(a_{i})\in \varDelta ^{*}$, $|\phi _{1}(a_{i})|$ represents the number of its suffixes. Then we need $m=|Q_{2}|\times |\varSigma |\times \prod _{a_{i}\in \varSigma }|\phi _{1}(a_{i})|$ steps in the proof I, while we just need $n=|Q_{2}|\times |\varSigma |$ steps in the proof II, that is, $n\ll m$, which means that the improved proof has greatly improved the efficiency of operation. From two different proofs above, it can be seen that the construction of new state sets is a particularly essential step and the key to improve the efficiency.

6 Conclusion

In this paper, we have studied fuzzy context-free grammars (FCFG), fuzzy context-free languages(FCFL) and fuzzy pushdown automata(FPDA) whose condomain forms a lattice-ordered monoid $\mathcal {L}$. Some important conclusions are obtained. Particularly, if $\mathcal {L}$ is commutative, we show an improved proof of the closure under homomorphic inverse of fuzzy context-free languages, which has greatly improved the efficiency of the operation by comparing with the classical method. Undoubtedly, much more work remains to be completed along this line. There may be more special properties of fuzzy context-free languages on lattice-ordered monoids.