# On Intuitionistic Fuzzy Context-Free Languages

Authors: Jianhua Jin; Qingguo Li; Chunquan Li
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

Taking intuitionistic fuzzy sets as the structures of truth values, we propose the notions of intuitionistic fuzzy context-free grammars (IFCFGs, for short) and pushdown automata with final states (IFPDAs). Then we investigate algebraic characterization of intuitionistic fuzzy recognizable languages including decomposition form and representation theorem. By introducing the generalized subset construction method, we show that IFPDAs are equivalent to their simple form, called intuitionistic fuzzy simple pushdown automata (IF-SPDAs), and then prove that intuitionistic fuzzy recognizable step functions are the same as those accepted by IFPDAs. It follows that intuitionistic fuzzy pushdown automata with empty stack and IFPDAs are equivalent by classical
automata theory. Additionally, we introduce the concepts of Chomsky normal form grammar (IFCNF) and Greibach normal form grammar (IFGNF) based on intuitionistic fuzzy sets. The results of our study indicate that intuitionistic fuzzy context-free languages generated by IFCFGs are equivalent to those generated by IFGNFs and IFCNFs, respectively, and they are also equivalent to intuitionistic fuzzy recognizable step functions. Then some operations on the family of intuitionistic fuzzy context-free languages are discussed. Finally, pumping lemma for intuitionistic fuzzy context-free languages is investigated.


---

## Body

## 1. Introduction

Intuitionistic fuzzy set (IFS) introduced by Atanassov [1–3], which emerges from the simultaneous consideration of the degrees of membership and nonmembership with a degree of hesitancy, has been found to be highly useful in dealing with problems with vagueness and uncertainty. The notion of vague set, proposed by Gau and Buehrer [4], is another generalization of fuzzy sets. However, Burillo and Bustince [5] showed that it is an equivalence of the IFS and studied intuitionistic fuzzy relations. Recently, IFS theory has supported a wealth of important applications in many fields such as fuzzy multiple attribute decision making, fuzzy pattern recognition, medical diagnosis, fuzzy control, and fuzzy optimization [6–10].In classical theoretical computer science, it is well known that formal languages are very useful in the description of natural languages and programming languages. But they are not powerful in the processing of human languages. For this, Lee and Zadeh [11] introduced the notion of fuzzy languages and gave some characterizations, where fuzzy languages took values in the unit interval [0,1]. Malik and Mordeson [12–14] studied algebraic properties of fuzzy languages. They stated that fuzzy regular languages can be characterized by fuzzy finite automata, fuzzy regular expressions, and fuzzy regular grammars. Meanwhile, as one of the generators of fuzzy languages, fuzzy automata have been used to solve meaningful issues such as the model of computing with words [15], clinical monitoring [16], neural networks [17], and pattern recognition [18]. Also, fuzzy grammars, automata, and languages tend to the improvement of lexical analysis and simulating fuzzy discrete event dynamical systems and hybrid systems [14, 19].As is well known, quantum logic was proved by Birkhoff and Von Neumann as a logic of quantum mechanics and is currently understood as a logic with truth values taken from an orthomodular lattice. To study quantum computation, Ying [20, 21] first proposed automata theory based on quantum logic where quantum automata are defined to be orthomodular lattice-valued generalization of classical automata. More systematic exposition of this theory appeared in [22, 23]. Moore and Crutchfield [24] defined quantum version of pushdown automata and regular and context-free grammars. He showed that the corresponding languages generated by quantum grammars and recognized by quantum automata have satisfactory properties in analogy to their classical counterparts. A basic framework of grammar theory on quantum logic was established by Cheng and Wang [25]. They proved that the set of lattice-valued quantum regular languages generated by lattice-valued quantum regular grammars coincides with that of lattice-valued quantum languages recognized by lattice-valued quantum automata. Then some algebraic properties of automata based on quantum logic were discussed by Qiu [26, 27]. To enhance the processing ability of fuzzy automata, the membership grades were extended to many general algebraic structures. For example, by combining the ideas in [20–23] and the idea in Ying's another work on topology based on residuated lattice-valued logic [28], Qiu has primarily established automata theory based on complete residuated lattice-valued logic [29–31]. And Li and Pedrycz [32] studied automata theory with membership values in lattice-ordered monoids. They showed that lattice-valued finite automata have more power to recognize fuzzy languages than that of classical fuzzy finite automata. Recently, Li [33] studied automata theory with membership values in lattices, introduced the technique of extended subset construction to prove the equivalence between lattice-valued finite automata and lattice-valued deterministic finite automata, and then presented a minimization algorithm of lattice-valued deterministic finite automata. On the basis of breadth-first and depth-first ways, Jin and Li [34] established a fundamental framework of fuzzy grammars based on lattices, which provided a necessary tool for the analysis of fuzzy automata.Fuzzy context-free languages, more powerful than fuzzy regular languages, have also been studied and can be characterized by fuzzy pushdown automata with two distinct ways and fuzzy context-free grammars, respectively [14, 35]. As a continuation of the work in [29–31], a fundamental framework of fuzzy pushdown automata theory based on complete residuated lattice-valued logic has been established in recent years by Xing et al. [36], and the work generalizes the previous fuzzy automata theory systematically studied by Mordeson and Malik to some extent. The pumping lemma for fuzzy context-free grammar theory in this setting was also investigated by Xing and Qiu [37].Using the notions of IFSs and fuzzy finite automata, Jun [38, 39] presented the concept of intuitionistic fuzzy finite state machines as a generalization of fuzzy finite state machines, and Zhang and Li [40] discussed intuitionistic fuzzy recognizers, intuitionistic fuzzy finite automata, and intuitionistic fuzzy language. They showed that the languages recognized by intuitionistic fuzzy recognizers are regular, and the intuitionistic fuzzy languages recognized by the intuitionistic fuzzy finite automata and the intuitionistic fuzzy languages recognized by deterministic intuitionistic fuzzy finite automata are equivalent. Recently Chen et al. [41] utilized the intuitionistic fuzzy automata to deal with consumers' advertising involvement when considering the expression of an IFS characterized by a pair of membership degree and nonmembership degree is similar to human thinking logic with pros and cons. Due to pushdown automata being another kind of important computational models [15] and also motivated by the importance of grammars, languages and models theory [14], it stands to reason that we ought consider the notions of intuitionistic fuzzy pushdown automata, intuitionistic fuzzy context-free grammars, and fuzzy context-free languages because our discussion in this paper will provide a fundamental framework for studying intuitionistic fuzzy set theory on fuzzy pushdown automata and generators as well. How to characterize intuitionistic fuzzy context-free languages and its pumping lemma in this setting becomes open problems; however, there is no research on the algebraic characterization of intuitionistic fuzzy context-free languages. We will try to solve the problems in this paper. Additionally, some examples are given to illustrate the significance of the results. In particular, Example 35 presented in this paper will show that intuitionistic fuzzy pushdown automata have more power than fuzzy pushdown automata when comparing two distinct strings although the degrees of membership of these strings recognized by the underlying fuzzy pushdown automata are equal. Investigating intuitionistic fuzzy context-free languages will reduce the gap between the precision of formal languages and the imprecision of human languages.The remaining parts of the paper are arranged as follows. Section2 describes some basic concepts of IFSs. Section 3 gives the definitions of intuitionistic fuzzy pushdown automata with two distinct ways and their languages. It is investigated that, for any intuitionistic fuzzy pushdown automaton with final states (IFPDA, for short), there is a cover, which consists of a collection of classical pushdown automata, equivalent to the IFPDA. By introducing intuitionistic fuzzy recognizable step functions, it is shown that intuitionistic fuzzy pushdown automata with final states and empty stack are intuitionistic fuzzy recognizable step functions, respectively, and conversely any intuitionistic fuzzy recognizable step function can be recognized by an intuitionistic fuzzy pushdown automaton with final states or empty stack. It follows that intuitionistic fuzzy pushdown automata with final states and empty stack are equivalent. Section 4 studies intuitionistic fuzzy context-free grammars (IFCFGs) as a type of generator of intuitionistic fuzzy context-free languages (IFCFLs). The notions of intuitionistic fuzzy Chomsky normal form (IFCNF) and Greibach normal form (IFGNF) are proposed. The results of our study indicate that IFCFLs generated by IFCFGs are equivalent to those generated by IFGNFs and IFCNFs, respectively, and they are also equivalent to intuitionistic fuzzy recognizable step functions. The algebraic properties of IFCFLs are also discussed. Section 5 establishes pumping lemma for IFCFLs. Some examples are then given to illustrate the application of pumping lemma and the significance of IFCFLs. Finally, conclusions and directions for future work are presented in Section 6.


## 2. Basic Concepts

Definition 1 (see [40]).
An intuitionistic fuzzy setA in a nonempty set X is an object having the form:
(1)A={(x,μA(x),νA(x))∣x∈X},
where the functions μA:X→[0,1] and νA:X→[0,1] denote the degree of membership (i.e., μA(x)) and the degree of nonmembership (νA(x)) of each element x∈X to the set A, respectively, and the two quantities satisfy the following inequalities:
(2)0≤μA(x)+νA(x)≤1,∀x∈X.
For the sake of simplicity, we use the notation A=(μA,νA) instead of A={(x,μA(x),νA(x))∣x∈X}. An intuitionistic fuzzy set will be abbreviated as an IFS.
Let{Ai∣i∈I} be a family of IFSs in X. Then the infimum and supremum operations of IFSs are defined as follows:
(3)⋂i∈I‍Ai={(x,⋀i∈IμAi(x),⋁i∈IνAi(x))∣x∈X},⋃i∈I‍Ai={(x,⋁i∈IμAi(x),⋀i∈IνAi(x))∣x∈X},
where ⋁ and ⋀ denote supremum and infimum of real numbers in [0,1], respectively.
For two IFSsA=(μA,νA) and B=(μB,νB), we say A=B if μA=μB and νA=νB. In addition, if the IFS A=(μA,νA) in X satisfies the condition that, for any x∈X, μA(x)+νA(x)=1, then A reduces to a fuzzy set in X. The difference between intuitionistic fuzzy sets and fuzzy sets is whether the sum of the degrees of membership and nonmembership of an element to a set equals one.
An IFR inX×Y is an intuitionistic fuzzy subset of X×Y; that is, it is an expression E given by
(4)E={((x,y),μE(x,y),νE(x,y))∣x∈X,y∈Y},
where the mappings μE:X×Y→[0,1] and νE:X×Y→[0,1] satisfy
(5)0≤μE(x,y)+νE(x,y)≤1,∀(x,y)∈X×Y.
An IFBR over X is an IFS of X×X. Let P=(μP,νP) and E=(μE,νE) be IFRs in X×Y and Y×Z, respectively. Define the composition of IFRs, P∘E=(μP∘E,νP∘E) in X×Z, by
(6)μP∘E(x,z)=⋁y∈Y(μP(x,y)∧μE(y,z)),νP∘E(x,z)=⋀y∈Y(νP(x,y)∨νE(y,z)),
for all (x,z)∈X×Z.
Furthermore, ifR is an IFBR over X, then its reflexive and transitive closure is R*=⋃n=0∞Rn, where Rn+1=Rn∘R,n≥0, and R0=id=(μid,νid), that is,
(7)μid(u,v)={1,ifu=v0,ifu≠v,νid(u,v)={0,ifu=v1,ifu≠v,
for all (u,v)∈X×X.Definition 2.
LetA=(μA,νA) be an IFS in X. Then the image set of A, denoted as Im(A), is given as
(8)Im(A)=Im(μA)∪Im(νA),
where Im(μA)={μA(x)∣x∈X} and Im(νA)={νA(x)∣x∈X}.
For anyλ,θ∈[0,1], λ+θ≤1, the (λ,θ)-cut set of A is defined as
(9)A(λ,θ)={x∈X∣μA(x)≥λ,νA(x)≤θ}.
And the support set of A, denoted as supp(A), is defined by
(10)supp(A)={x∈X∣μA(x)>0,νA(x)<1}.
If supp(A) is finite, then A is called a finite IFS in X.


## 3. Intuitionistic Fuzzy Pushdown Automata

It is well known that any language accepted by a pushdown automaton with final states can be accepted by a certain pushdown automaton with empty stack, and vice versa. As a natural generalization of pushdown automata, we give the notions of intuitionistic fuzzy pushdown automata with final states and empty stack, respectively, and then do research in the algebraic characterization of their intuitionistic fuzzy recognizable languages including decomposition form and representation theorem. Note thatΣ* is the free monoid generated from the set Σ with the operator of concatenation, where the empty string ε is identified with the identity of  Σ. And the length of the string ω∈Σ* is denoted by |ω|. Nk={1,…,k}.Definition 3.
An intuitionistic fuzzy pushdown automaton with final states (IFPDA, for short) is a seven tupleℳ=(Q,Σ,Γ,δ,I,Z0,F), where(i)
Qis a finite nonempty set of states;(ii)
Σ is a finite nonempty set of input symbols;(iii)
Γ is a finite nonempty set of stack symbols;(iv)
δ=(μδ,νδ) is a finite IFS in Q×(Σ∪{ε})×Γ×Q×Γ*;(v)
Z0∈Γ is called the start stack symbol;(vi)
I=(μI,νI) and F=(μF,νF) are intuitionistic fuzzy subsets in Q, which are called the intuitionistic fuzzy subsets of initial and final states, respectively.Definition 4.
An intuitionistic fuzzy pushdown automaton with empty stack (IFPDA∅, for short) is a seven tuple 𝒩=(Q,Σ,Γ,δ,I,Z0,∅), where Q,Σ,Γ,δ,I and Z0 are the same as those in IFPDA ℳ, and ∅ represents an empty set.Definition 5.
Letℳ=(Q,Σ,Γ,δ,I,Z0,F) be an IFPDA. Define an IFBR on Q×Σ*×Γ*, ⊢ℳ=(μ⊢ℳ,ν⊢ℳ) in the form of
(11)μ⊢ℳ((q,ω,β),(p,u,α))={μδ(q,ε,head(β),p,α∖tail(β)),ifu=ω,tail(β)≤αμδ(q,head(ω),head(β),p,α∖tail(β)),ifu=tail(ω),tail(β)≤α0,otherwise,ν⊢ℳ((q,ω,β),(p,u,α))={νδ(q,ε,head(β),p,α∖tail(β)),ifu=ω,tail(β)≤ανδ(q,head(ω),head(β),p,α∖tail(β)),ifu=tail(ω),tail(β)≤α0,otherwise
for any (q,ω,β),(p,u,α)∈Q×Σ*×Γ*. Here, for any nonempty string u=x1⋯xn, n≥1, head(u)=x1, tail(u)=x2⋯xn, and tail(u)≤u. ⊢ℳ* is the reflexive and transitive closure of ⊢ℳ.
If no confusion, we denote⊢ and ⊢* instead of  ⊢ℳ and ⊢ℳ*, respectively.Definition 6.
Letℳ=(Q,Σ,Γ,δ,I,Z0,F) be an IFPDA. Then we call ℒ(ℳ) an intuitionistic fuzzy language accepted by ℳ with final states, where ℒ(ℳ)=(μℒ(ℳ),νℒ(ℳ)), μℒ(ℳ), and νℒ(ℳ) are functions from Σ* to the unit interval [0,1], andμℒ(ℳ)(ω)
=⋁{μI(q0)∧μ⊢ℳ*((q0,ω,z0), (p,ε,r))∧ μF(p)∣q0,p∈Q,r∈Γ*},νℒ(ℳ)(ω) = ⋀{νI(q0)∨ν⊢ℳ*((q0,ω,z0), (p,ε,r))∨νF (p)∣q0,p∈Q,r∈Γ*}for any ω∈Σ*.Definition 7.
Let𝒩=(Q,Σ,Γ,δ,I,Z0,∅) be an IFPDA∅. Then we call ℒ(𝒩) an intuitionistic fuzzy language accepted by 𝒩 with empty stack, where ℒ(𝒩)=(μℒ(𝒩),νℒ(𝒩)), μℒ(𝒩) and νℒ(𝒩) are functions from Σ* to the unit interval [0,1], andμℒ(𝒩)(ω) = ⋁{μI(q0)∧μ⊢𝒩*((q0,ω,z0), (p,ε,ε))∣q0,p∈Q},νℒ(𝒩)(ω) = ⋀{νI(q0)∨v⊢𝒩*((q0,ω,z0),(p,ε,ε))∣q0,p∈Q}for any ω∈Σ*.Lemma 8 (see [33]).
Letl be a lattice and X a finite subset of l. Then the ∧-semilattice of l generated by X, written as X∧, is finite, and the ∨-semilattice of l generated by X, denoted as X∨, is also finite, where X∧={x1∧⋯∧xk:k≥1,x1,…,xk∈X}∪{1}, and X∨={x1∨⋯∨xk:k≥1,x1,…,xk∈X}∪{0}.Proposition 9.
Iff can be accepted by some IFPDA ℳ=(Q,Σ,Γ,δ,I,Z0,F), then f is an IFS in Σ*, and the image set of f is finite.Proof.
We have the following.
Claim1 (f=(μf,νf) is an IFS in Σ*).
It suffices to show that0≤μf(ω)+νf(ω)≤1, for any ω=u1⋯un, ui∈Σ∪{ε}, i=1,…,n.
Clearly,μf(ω)=⋁{μI(q0)∧μ⊢ℳ*((q0, ω,z0),(p,ε,r))∧μF(p)∣q0,p∈Q,r∈Γ*} = ⋁{μI(q0)∧μ⊢((q0,ω,z0), (q1,u2⋯un,z1r1))∧μ⊢((q1,u2⋯un,z1r1),(q2,u3⋯un, z2r2))∧⋯∧μ⊢((qn-1, un,zn-1rn-1), (qn,ε,rn))∧μF(qn)∣(q0,q1,…,qn)∈Qn+1,z1,…,zn-1∈Γ, r1,…,rn∈Γ*}, and νf(ω)=⋀{νI(q0)∨ν⊢ℳ*((q0, ω,z0),(p,ε,r))∨νF(p)∣q0,p∈Q,r∈Γ*} = ⋀{νI(q0)∨ν⊢((q0,ω,z0), (q1,u2⋯un,z1r1))∨ν⊢((q1, u2⋯un,z1r1), (q2,u3⋯un,z2r2))∨⋯∨ν⊢((qn-1, un,zn-1rn-1), (qn,ε,rn))∨νF(qn)∣(q0,q1,…,qn)∈Qn+1,z1, …,zn-1∈Γ, r1,…,rn∈Γ*}.
On the one hand,0≤μf(ω)+νf(ω); on the other hand, there exists a sequence (q0,q1,…,qn)∈Qn+1,z1, …,zn-1∈Γ,r1,…,rn∈Γ* such that μf(ω)=μI(q0)∧μ⊢((q0,ω,z0), (q1,u2⋯un, z1r1))∧μ⊢((q1,u2⋯un, z1r1), (q2,u3⋯un, z2r2)) ∧⋯∧μ⊢((qn-1,un, zn-1rn-1), (qn,ε,rn))∧μF(qn). Hence νf(ω)≤νI(q0)∨ν⊢((q0, ω,z0), (q1,u2⋯un, z1r1))∨ν⊢((q1,u2⋯un,z1r1), (q2,u3⋯un, z2r2))∨⋯∨ν⊢((qn-1,un, zn-1rn-1), (qn,ε,rn))∨νF(qn).
Therefore,μf(ω)+νf(ω)≤(μI(q0)+νI(q0))∨(μ⊢((q0,ω,z0),(q1,u2⋯un,z1r1))+ν⊢((q0,ω,z0), (q1,u2⋯un,z1r1)))∨(μ⊢((q1,u2⋯un,z1r1),(q2,u3⋯un,z2r2))+ν⊢((q1,u2⋯un,z1r1), (q2,u3⋯un,z2r2)))∨⋯∨(μ⊢((qn-1,un,zn-1rn-1), (qn,ε,rn))+ν⊢((qn-1,un,zn-1rn-1), (qn,ε,rn)))∨(μF(qn)+νF(qn))≤1∨1∨⋯∨1=1.
Claim2 (Im(f) is finite).
In fact, letX=Im(μI)∪Im(μδ)∪Im(μF) and Y=Im(νI)∪Im(νδ)∪Im(νF). Then X∧={x1∧⋯∧xk∣k≥1,x1, …,xk∈X}∪{1} and X∨={x1∨⋯∨xk∣k≥1,x1,…,xk∈X}∪{0} are finite sets by Lemma 8. Since δ=(μδ,νδ) is a finite IFS, for any ω=u1⋯un, ui∈Σ∪{ε}, i=1,…,n, there exists a natural number d∈N such that μf(ω)=⋁{μI(q0)∧μ⊢((q0,ω,z0), (q1,u2⋯un,z1r1))∧μ⊢((q1,u2⋯un,z1r1), (q2,u3⋯un,z2r2))∧⋯∧μ⊢((qn-1,un,zn-1rn-1), (qn,ε,rn))∧μF(qn)∣(q0,q1,…,qn)∈Qn+1, z1,…,zn-1∈Γ, r1,…,rn∈Γ*} = (a10∧⋯∧a1,n-1∧a1n)∨⋯∨(ad0∧⋯∧ad,n-1∧adn)), where aij∈X, i=1,…,d; j=0,…,n. By Lemma 8, (X∧)∨ is also finite. Since μf(ω)∈(X∧)∨ for any ω∈Σ*, Im(μf)⊆(X∧)∨. Hence Im(μf) is a finite subset of [0,1].
Similarly, it follows thatIm(νf) is also a finite subset of [0,1].
Therefore,Im(f)=Im(μf)∪Im(νf) is finite.
Iff can be accepted by some IFPDA∅𝒩=(Q,Σ,Γ,δ,I,Z0,∅), then, by Definition 7, for any ω=u1⋯un, ui∈Σ∪{ε}, i=1,…,n, we have μf(ω)=⋁{μI(q0)∧μ⊢𝒩*((q0,ω,z0), (p,ε,ε))∣q0,p∈Q} = ⋁{μI(q0)∧μ⊢((q0,ω,z0),(q1,u2⋯un,z1r1))∧μ⊢((q1,u2⋯un,z1r1), (q2,u3⋯un,z2r2))∧⋯∧μ⊢((qn-1,un,zn-1rn-1), (qn,ε,ε))∣(q0,q1,…,qn)∈Qn+1, z1,…,zn-1∈Γ,r1,…,rn-1∈Γ*}, and νf(ω)=⋀{νI(q0)∨ν⊢𝒩*((q0,ω,z0), (p,ε,ε))∣q0,p∈Q}=⋀{νI(q0)∨ν⊢((q0,ω,z0), (q1,u2⋯un,z1r1))∨ν⊢((q1, u2⋯un,z1r1),(q2,u3⋯un, z2r2))∨⋯∨ν⊢((qn-1,un,zn-1rn-1), (qn,ε,ε))∣(q0,q1,…,qn)∈Qn+1, z1,…,zn-1∈Γ,r1,…,rn-1∈Γ*}.
In a similar manner, it is concluded that the following must be true.Proposition 10.
Iff can be accepted by some IFPDA∅𝒩=(Q,Σ,Γ,δ,I,Z0,∅), then f is an IFS in Σ*, and the image set of f is finite.Specially, the IFPDAℳ=(Q,Σ,Γ,δ,I,Z0,F) will be abbreviated as ℳ′=(Q,Σ,Γ,δ,q0,Z0,F), whenever Im(I)⊆{0,1} and supp(I)={q0}. Moreover, if Im(I)∪Im(F)∪Im(δ)⊆{0,1} and supp(I) has only one element, then the IFPDA is a classical PDA.For two IFPDAsℳ1 and ℳ2, we say that they are equivalent if they accept the same intuitionistic fuzzy language.Proposition 11.
LetA be an IFS in a nonempty set Σ*. Then the following statements are equivalent:(i)
Acan be accepted by an IFPDAℳ=(Q,Σ,Γ,δ,I,Z0,F);(ii)
Acan be accepted by a certain IFPDAℳ′=(Q′,Σ,Γ′,δ′,q0,X0,F′), where q0∈Q′.Proof.
(i) implies (ii). Construct an IFPDAℳ′=(Q′,Σ,Γ′,δ′,I′,X0,F′) as follows: Q′=Q∪{q0}, Γ′=Γ∪{X0}, where q0∉Q, X0∉Γ. Define an IFS I′ in Q′ by
(12)μI′(q)={1,ifq=q00,ifq≠q0,νI′(q)={0,ifq=q01,ifq≠q0.
Define an IFSF′ in Q′ by
(13)μF′(q)={0,ifq=q0μF(q),ifq≠q0,νF′(q)={1,ifq=q0νF(q),ifq≠q0.
Define an IFSδ′ in Q′×(Σ∪{ε})×Γ′×Q′×Γ′* by mappings μδ′,νδ′:Q′×(Σ∪{ε})×Γ′×Q′×Γ′*→[0,1], μδ′(q0,ε,X0,p,Z0)=μI(p), νδ′(q0,ε,X0,p,Z0)=νI(p), μδ′(q,τ,z,p,γ)=μδ(q,τ,z,p,γ), νδ′(q,τ,z,p,γ)=νδ(q,τ,z,p,γ), where q,p∈Q, τ∈Σ∪{ε}, z∈Γ, γ∈Γ*; otherwise, μδ′(q0,τ,z,p,γ)=0 and νδ′(q0,τ,z,p,γ)=1.
Then for anyω=u1⋯un∈Σ*, ui∈Σ∪{ε},i=1,…,n, we have μℒ(ℳ′)(ω)=⋁{μI′(q)∧μ⊢ℳ′((q,ω,X0), (p0,ω,Z0))∧μ⊢ℳ′((p0,ω,Z0), (q1,u2⋯un,z1r1))∧μ⊢ℳ′((q1,u2⋯un,z1r1), (q2,u3⋯un,z2r2))∧⋯∧μ⊢ℳ′((qn-1,un,zn-1rn-1),(qn,ε,rn))∧μF′(qn)∣q∈Q′, (p0,q1,…,qn)∈Q′n+1,z1,…,zn-1∈Γ′,  r1,…,rn∈Γ′*}=⋁{1∧μI(p0)∧μ⊢ℳ((p0,ω,Z0),(q1,u2⋯un,z1r1))∧μ⊢ℳ((q1,u2⋯un,z1r1),(q2,u3⋯un,z2r2))∧⋯∧μ⊢ℳ((qn-1,un,zn-1rn-1),(qn,ε,rn))∧μF(qn)∣(p0,q1,…,qn)∈Qn+1,z1,…,zn-1∈Γ,r1,…,rn∈Γ*}=μℒ(ℳ)(ω), and νℒ(ℳ′)(ω)=⋀{νI′(q)∨ν⊢ℳ′((q,ω,X0),(p0,ω,Z0))∨ν⊢ℳ′((p0,ω,Z0), (q1,u2⋯un,z1r1))∨ν⊢ℳ′((q1,u2⋯un,z1r1), (q2,u3⋯un,z2r2))∨⋯∨ν⊢ℳ′((qn-1,un,zn-1rn-1), (qn,ε,rn))∨νF′(qn)∣q∈Q′, (p0,q1,…,qn)∈Q′n+1,z1,…,zn-1∈Γ′, r1,…,rn∈Γ′*}=⋀{1∨νI(p0)∨ν⊢ℳ((p0, ω,Z0),(q1,u2⋯un, z1r1))∨ν⊢ℳ((q1,u2⋯un,z1r1), (q2,u3⋯un,z2r2))∨⋯∨ν⊢ℳ((qn-1, un,zn-1rn-1),(qn,ε,rn))∨νF(qn)∣(p0,q1, …,qn)∈Qn+1,z1,…,zn-1∈Γ,  r1,…,rn∈Γ*}=νℒ(ℳ)(ω). Therefore, ℒ(ℳ′)=ℒ(ℳ).
From the construction, it is clearly thatℳ′ can be denoted as ℳ′=(Q′,Σ,Γ′,δ′,q0,X0,F′).
(ii) implies (i). Suppose the IFSA is accepted by the IFPDA ℳ′=(Q′,Σ,Γ′,δ′,q0,X0,F′). Then we construct an IFS I in Q′ by
(14)μI(q)={1,ifq=q00,ifq≠q0,νI(q)={0,ifq=q01,ifq≠q0.
It follows that the IFPDAℳ=(Q′,Σ,Γ′,δ′,I,X0,F′) accepts A.
Similarly, it is easily concluded that the following must be true.Proposition 12.
LetA be an IFS in a nonempty set Σ*. Then the following statements are equivalent:(i)
Acan be accepted by an IFPDA∅ℳ=(Q,Σ,Γ,δ,I,Z0,∅);(ii)
There exists an IFPDA∅ℳ′=(Q′,Σ,Γ′,δ′,q0,X0,∅)recognizingA, whereq0∈Q′.There is especially a simple type of intuitionistic fuzzy pushdown automata, which is called intuitionistic fuzzy simple pushdown automata. The definition is given as follows.Definition 13.
An IFPDAℳ=(Q,Σ,Γ,δ,q0,Z0,F) is called an intuitionistic fuzzy simple pushdown automaton (IFSPDA) if the image set of δ is contained in the set {0,1}.Next any IFPDA is proven to be an equivalence of a certain IFSPDA by utilizing the generalized subset construction method. Noting that an IFS requires that the sum of the degrees of membership and nonmembership of an element to a set is no more than the natural number 1. So the proof technique is to some extent different from the technique of extended subset construction introduced by Li in [33], and it is not an easy task to conduct reasoning in the realm of the modified techniques.Proposition 14.
Letℳ be an IFPDA. Then there exists an IFSPDA ℳ′ such that ℒ(ℳ′)=ℒ(ℳ).Proof.
Letℳ=(Q,Σ,Γ,δ,q0,Z0,F) be an IFPDA. Then we construct an IFSPDA  ℳ′=(Q′,Σ,Γ,δ′,q0′,Z0,F′) as follows:(i)
Q′=Q×(L1-{0})×(L2-{1}), where L1=X∧, L2=Y∨, X=Im(μδ)∪Im(μF) and Y=Im(νδ)∪Im(νF);(ii)
q0′=(q0,1,0)∈Q′;(iii)
δ′=(μδ′,νδ′) is an IFS in Q′×(Σ∪{ε})×Γ×Q′×Γ*, where the mappings μδ′,νδ′:Q′×(Σ∪{ε})×Γ×Q′×Γ*→{0,1} are given as follows. For any (q,a,b),(q′,c,d)∈Q′,τ∈Σ∪{ε}, X∈Γ and γ∈Γ*, μδ′((q,a,b),τ,X,(q′,c,d),γ)=1, and νδ′((q,a,b),τ,X,(q′,c,d),γ)=0 whenever there exist a′ and b′ such that μδ(q,τ,X,q′,γ)=a′>0, νδ(q,τ,X,q′,γ)=b′<1, c=a∧a′ and d=b∨b′. Otherwise, μδ′((q,a,b),τ,X,(q′,c,d),γ)=0 and νδ′((q,a,b),τ,X,(q′,c,d),γ)=1;(iv)
F′=(μF′,νF′) is an IFS in Q′. For any (q,a,b)∈Q′,
(15)μF′((q,a,b))={a∧μF(q),if0≤a+b≤10,ifa+b>1,νF′((q,a,b))={b∨νF(q),if0≤a+b≤11,ifa+b>1.
Now, it is claimed that, for anyω=τ1⋯τn∈Σ*, τi∈Σ∪{ε}, i∈{1,…,n} and for any (qn,an,bn)∈Q′, Zn,γn∈Γ*, μ⊢ℳ′*((q0′,ω,Z0),((qn,an,bn),ε,Znγn))=1 and ν⊢ℳ′*((q0′,ω,Z0),((qn,an,bn),ε,Znγn))=0 whenever the following condition is satisfied.
(P1) There existq1,…,qn-1∈Q, Z1,…,Zn-1∈Γ and γ1,…,γn-1∈Γ* such that an=μ⊢ℳ((q0,ω,Z0), (q1,τ2⋯τn,Z1γ1))∧μ⊢ℳ((q1,τ2⋯τn,Z1γ1), (q2,τ3⋯τn,Z2γ2))∧⋯∧μ⊢ℳ((qn-1,τn,Zn-1γn-1), (qn,ε,Znγn)) and bn=ν⊢ℳ((q0,ω,Z0), (q1,τ2⋯τn,Z1γ1))∨ν⊢ℳ((q1,τ2⋯τn,Z1γ1), (q2,τ3⋯τn,Z2γ2))∨⋯∨ν⊢ℳ((qn-1,τn,Zn-1γn-1), (qn,ε,Znγn)). Otherwise, μ⊢ℳ′*((q0′,ω,Z0),((qn,an,bn),ε,Znγn))=0 and ν⊢ℳ′*((q0′,ω,Z0),((qn,an,bn),ε,Znγn))=1.
It is proved by induction. In fact, if|ω|=0, then ω=ε, μ⊢ℳ′*((q0,ε,Z0),(q0,ε,Z0))=1 and ν⊢ℳ*((q0,ε,Z0),(q0,ε,Z0))=0. Hence μ⊢ℳ*(((q0,1,0),ε,Z0),((q0,1,0),ε,Z0))=1 and ν⊢ℳ′*(((q0,1,0),ε,Z0),((q0,1,0),ε,Z0))=0.
Suppose the result still holds whenever|ω|≤n, n∈N. If |ω|=n+1, ω=τ1⋯τkτk+1=xτk+1 and τk+1∈Σ, then |x|=n and x=τ1⋯τk.
Next, for any(qk+1,ak+1,bk+1)∈Q′, Zk+1,γk+1∈Γ*, whenever (P1) is satisfied; that is, there exists a sequence of states q1,…,qk∈Q, Z1,…,Zk∈Γ, γ1,…,γk∈Γ* such thatμ⊢ℳ((qi,τi+1⋯τk+1,Ziγi), (qi+1,τi+2⋯τk+1, Zi+1γi+1)) = ci+1>0,ν⊢ℳ((qi,τi+1⋯τk+1,Ziγi), (qi+1,τi+2⋯τk+1, Zi+1γi+1)) = di+1<1,μδ(qk,τk+1,Zk,qk+1,Zk+1)=ck+1>0,νδ(qk,τk+1,Zk,qk+1,Zk+1)=dk+1<1,where γ0=ε, i=0,1,…,k-1.
Letal=c1∧⋯∧cl, bl=d1∨⋯∨dl, l∈{1,…,k+1}. Thenμ⊢ℳ′(((qi,ai,bi),τi+1⋯τk+1,Ziγi),((qi+1,ai+1,bi+1), τi+2⋯τk+1,Zi+1γi+1)) = 1,ν⊢ℳ′(((qi,ai,bi),τi+1⋯τk+1,Ziγi), ((qi+1,ai+1,bi+1), τi+2⋯τk+1,Zi+1γi+1))=0,μ⊢ℳ′(((qk,ak,bk),τk+1,Zkγk),((qk+1,ak+1,bk+1), ε,Zk+1γk+1))=1, andν⊢ℳ′(((qk,ak,bk),τk+1,Zkγk),((qk+1,ak+1,bk+1), ε,Zk+1γk+1))=0,where a0=1, b0=0, γ0=ε, i=0,1,…,k-1.
By assumption,μ⊢ℳ′*((q0′,x,Z0), ((qk,ak,bk),ε,Zkγk))=1,  ν⊢ℳ′*((q0′,x,Z0), ((qk,ak,bk),ε,Zkγk))=0, and so μ⊢ℳ′*((q0′,xτk+1,Z0), ((qk,ak,bk),τk+1,Zkγk))=1, ν⊢ℳ′*((q0′,xτk+1,Z0), ((qk,ak,bk), τk+1,Zkγk))=0.
Therefore,μ⊢ℳ′*((q0′,ω,Z0), ((qk+1,ak+1,bk+1), ε,Zk+1γk+1))=⋁{μ⊢ℳ′*((q0′,ω,Z0), ((qk,ak,bk), τk+1,Zkγk))∧μ⊢ℳ′(((qk,ak,bk),τk+1,Zkγk), ((qk+1,ak+1,bk+1), ε,Zk+1γk+1))∣(qk,ak,bk)∈Q′, Zk∈Γ,γk∈Γ*}=1∧1=1.
ν
⊢
ℳ
′
*
(
(
q
0
′
,
ω
,
Z
0
), ((qk+1,ak+1,bk+1), ε,Zk+1γk+1)) = ⋀{ν⊢ℳ′*((q0′,ω,Z0), ((qk,ak,bk), τk+1,Zkγk))∨ν⊢ℳ′(((qk,ak,bk),τk+1,Zkγk), ((qk+1,ak+1,bk+1), ε,Zk+1γk+1))∣(qk,ak,bk)∈Q′,Zk∈Γ,γk∈Γ*}=0∨0=0.
For any(qk+1,ak+1,bk+1)∈Q′, Zk+1,γk+1∈Γ*, if (P1) is not satisfied, then it follows thatμ⊢ℳ′*((q0′,ω,Z0),((qk+1,ak+1,bk+1),ε,Zk+1γk+1))=0,ν⊢ℳ′*((q0′,ω,Z0),((qk+1,ak+1,bk+1),ε,Zk+1γk+1))=1.
Hence, for anyω=τ1⋯τn∈Σ*, τi∈Σ∪{ε}, i∈{1,…,n}, we have μℒ(ℳ′)(ω)=⋁{μ⊢ℳ′*((q0′,ω,Z0), ((qn,an,bn),ε, γ))∧μF′((qn,an,bn))∣(qn, an,bn)∈Q′,γ∈Γ*} = ⋁{an∧μF(qn)∣q1,…,qn-1∈Q, Z1,…,Zn-1∈Γ, γ1,…,γn-1∈Γ*, an=μ⊢ℳ((q0,ω,Z0), (q1,τ2⋯τn, Z1γ1))∧μ⊢ℳ((q1,τ2⋯τn,Z1γ1), (q2,τ3⋯τn,Z2γ2))∧⋯∧μ⊢ℳ((qn-1, τn,Zn-1γn-1),(qn,ε,γ)), bn=ν⊢ℳ((q0,ω,Z0), (q1,τ2⋯τn,Z1γ1))∨ν⊢ℳ((q1,τ2⋯τn,Z1γ1),    (q2,τ3⋯τn,Z2γ2))∨⋯∨ν⊢ℳ((qn-1,  τn,Zn-1γn-1), (qn,ε,γ))}=⋁{μ⊢ℳ((q0,ω,Z0),(q1,τ2⋯τn,Z1γ1))∧μ⊢ℳ((q1,τ2⋯τn,Z1γ1),(q2,τ3⋯τn, Z2γ2))∧⋯∧μ⊢ℳ((qn-1, τn,Zn-1γn-1),(qn,ε,γ))∧μF(qn)∣q1,…,qn-1∈Q,Z1,…,Zn-1∈Γ, γ1,…,γn-1∈Γ*}=μℒ(ℳ)(ω), νℒ(ℳ′)(ω)=⋀{ν⊢ℳ′*((q0′,ω,Z0), ((qn,an,bn),ε, γ))∨νF′((qn,an,bn))∣(qn,an,bn)∈Q′, γ∈Γ*}=⋀{bn∨νF(qn)∣q1,…,qn-1∈Q, Z1,…,Zn-1∈Γ, γ1,…,γn-1∈Γ*, an=μ⊢ℳ((q0,ω,Z0),(q1,τ2⋯τn,Z1γ1))∧μ⊢ℳ((q1, τ2⋯τn,Z1γ1),(q2,τ3⋯τn,Z2γ2))∧⋯∧μ⊢ℳ((qn-1, τn,Zn-1γn-1),(qn,ε,γ)), bn=ν⊢ℳ((q0,ω,Z0), (q1,τ2⋯τn,Z1γ1))∨ν⊢ℳ((q1,τ2⋯τn,Z1γ1), (q2,τ3⋯τn,Z2γ2))∨⋯∨ν⊢ℳ((qn-1, τn,Zn-1γn-1), (qn,ε,γ))}=⋀{ν⊢ℳ((q0,ω,Z0), (q1,τ2⋯τn,Z1γ1))∨ν⊢ℳ((q1, τ2⋯τn,Z1γ1),(q2,τ3⋯τn, Z2γ2))∨⋯∨ν⊢ℳ((qn-1,τn,Zn-1γn-1), (qn,ε,γ))∨νF(qn)∣q1,…,qn-1∈Q,Z1,…,Zn-1∈Γ, γ1,…,γn-1∈Γ*}=νℒ(ℳ)(ω).
Therefore,ℒ(ℳ′)=ℒ(ℳ).Clearly, an IFPDA is a generalization of a classical pushdown automaton (PDA). Next, it will be shown that any IFPDA can be characterized by a collection of pushdown automata. To describe the behavior of a pushdown automatonℳ=(Q,Σ,Γ,δ,q0,Z0,F), we need to introduce the concept of instantaneous description. An instantaneous description is a three-tuple (q,ω,γ)∈Q×Σ*×Γ*, which means that the automaton is in the state q and has unexpended input ω and stack contents γ. An instantaneous description represents the configuration of a pushdown automaton at a given instant. To introduce the transition in a pushdown automaton in terms of instantaneous descriptions, we define ≻ℳ as a binary relation on Q×Σ*×Γ*. We say (q,aω,Zγ)≻ℳ(p,ω,σγ) if δ(q,a,Z) contains (p,σ), where p,q∈Q, a∈Σ∪{ε}, ω∈Σ*, Z∈Γ, and γ,σ∈Γ*. Furthermore, we define ≻ℳ* as the reflexive and transitive closure of ≻ℳ. Then the language accepted by ℳ with final states is defined as
(16)ℒ(ℳ)={ω∈Σ*∣(q0,ω,Z0)≻ℳ*(p,ε,γ),p∈F,γ∈Γ*}.Definition 15.
A collection of classical pushdown automata with final states(17)S={ℳab∣ℳab=(Q,Σ,Γ,δ,q0,Z0,Fab),0≤a+b≤1,a,b∈[0,1]{ℳabℳab=(Q,Σ,Γ,δ,q0,Z0,Fab)}}
is called a cover if the following conditions hold:(i)
a1≤a2 and b2≤b1 imply Fa2b2⊆Fa1b1;(ii)
F01=Q.
For a coverS, its recognized intuitionistic fuzzy language fS=(μfS,νfS) in Σ* is given byμfS(ω)=⋁{a∈[0,1]∣ℳab accepts  ω,ℳab∈S},νfS(ω)=⋀{b∈[0,1]∣ℳab accepts ω,ℳab∈S}, for all ω∈Σ*.Theorem 16.
Letf be an IFS in Σ*. Then f can be accepted by an IFPDA if and only if f can be recognized by a cover S.Proof.
Iff can be accepted by an IFPDA, then there exists an IFSPDA ℳ=(Q,Σ,Γ,δ,q0,Z0,F) such that ℳ accepts f by Proposition 14. Next we construct a cover
(18)S={ℳab∣ℳab=(Q,Σ,Γ,δ′,q0,Z0,Fab),0≤a+b≤1,a,b∈[0,1]{ℳabℳab=(Q,Σ,Γ,δ′,q0,Z0,Fab)}},
where Fab={q∈Q∣μF(q)≥a,νF(q)≤b}; the mapping δ′:Q×(Σ∪{ε})×Γ→2Q×Γ* is given byδ′(q,τ,Z)={(p,γ)∣μδ(q,τ,Z,p,γ)=1,p∈Q,γ∈Γ*}, for all (q,τ,Z)∈Q×(Σ∪{ε})×Γ.
Clearly, the coverS is well defined.
Next, we will show thatf can be recognized by the cover S. In fact, we have(q0,ω,Z0)≻ℳab*(q,ε,γ) if and only if μ⊢ℳ*((q0,ω,Z0),(q,ε,γ))=1,for all a,b∈[0,1] with a+b≤1, for all ω∈Σ*,γ∈Γ*. μfS(ω)=⋁{a∈[0,1]∣ℳab accepts ω,ℳab∈S}=⋁{a∈[0,1]∣q∈Fab,(q0,ω,Z0)≻ℳab*(q,ε,γ),γ∈Γ*}=⋁{a∈[0,1]∣μF(q)≥a,νF(q)≤b,(q0,ω,Z0)≻ℳab*(q,ε,γ),γ∈Γ*}=⋁{a∈[0,1]∣μF(q)≥a,(q0,ω,Z0)≻ℳab*(q,ε,γ),q∈Q,γ∈Γ*}=⋁{μF(q)∣μ⊢ℳ*((q0,ω,Z0),(q,ε,γ))=1,q∈Q,γ∈Γ*}=μf(ω)=μℒ(ℳ)(ω), νfS(ω)=⋀{b∈[0,1]∣ℳab accepts ω,ℳab∈S}=⋀{b∈[0,1]∣q∈Fab,(q0,ω,Z0)≻ℳab*(q,ε,γ),γ∈Γ*}=⋀{b∈[0,1]∣μF(q)≥a,νF(q)≤b,(q0,ω,Z0)≻ℳab*(q,ε,γ),γ∈Γ*}=⋀{b∈[0,1]∣νF(q)≤b,(q0,ω,Z0)≻ℳab*(q,ε,γ),q∈Q,γ∈Γ*}=⋀{νF(q)∣μ⊢ℳ*((q0,ω,Z0),(q,ε,γ))=1,q∈Q,γ∈Γ*}=νf(ω)=νℒ(ℳ)(ω).
Therefore,fS=ℒ(ℳ)=f.
Conversely, supposef can be recognized by a cover
(19)S={ℳab∣ℳab=(Q,Σ,Γ,δ′,q0,Z0,Fab),0≤a+b≤1,a,b∈[0,1]{ℳabℳab=(Q,Σ,Γ,δ′,q0,Z0,Fab)}}.
Then we construct an IFSPDA ℳ=(Q,Σ,Γ,η,q0,Z0,F), where η=(μη,νη) is an IFS in Q×(Σ∪{ε})×Γ×Q×Γ*, and the mappings μη,νη:Q×(Σ∪{ε})×Γ×Q×Γ*→{0,1} are defined as
(20)μη(q,τ,Z,p,γ)={1,if(p,γ)∈δ′(q,τ,Z)0,otherwise,νη(q,τ,Z,p,γ)={0,if(p,γ)∈δ′(q,τ,Z)1,otherwise,
for any (q,τ,Z,p,γ)∈Q×(Σ∪{ε})×Γ×Q×Γ*.
F
=
(
μ
F
,
ν
F
) is an IFS in Q, where μF(q)=⋁{a∈[0,1]∣q∈Fab} and νF(q)=⋀{b∈[0,1]q∈Fab},forallq∈Q. Then ℒ(ℳ)=fS. In fact, for any ω∈Σ*, μℒ(ℳ)(ω)=⋁{μF(q)∣μ⊢ℳ*((q0,ω,Z0),(q,ε,γ))=1,q∈Q,γ∈Γ*}=⋁{⋁{a∈[0,1]∣q∈Fab}∣μ⊢ℳ*((q0,ω,Z0),(q,ε,γ))=1,q∈Q,γ∈Γ*}=⋁{a∈[0,1]∣q∈Fab,μ⊢ℳ*((q0,ω,Z0),(q,ε,γ))=1,q∈Q,γ∈Γ*}=⋁{a∈[0,1]∣q∈Fab,(q0,ω,Z0)≻ℳab*(q,ε,γ),γ∈Γ*}=⋁{a∈[0,1]∣ℳab accepts ω,ℳab∈S}=μfS(ω), νℒ(ℳ)(ω)=⋀{νF(q)∣μ⊢ℳ*((q0,ω,Z0),(q,ε,γ))=1,q∈Q,γ∈Γ*}=⋀{⋀{b∈[0,1]∣q∈Fab}∣μ⊢ℳ*((q0,ω,Z0),(q,ε,γ))=1,q∈Q,γ∈Γ*}=⋀{b∈[0,1]∣q∈Fab,(q0,ω,Z0)≻ℳab*(q,ε,γ),γ∈Γ*}=⋀{b∈[0,1]∣ℳab accepts ω,ℳab∈S}=νfS(ω).
Therefore, the IFSPDAℳ accepts f.Theorem16 shows that every IFPDA is equivalent to a certain cover; however, the cover may have infinite classical pushdown automata elements. Is there a finite cover who is equivalent to the IFPDA? To solve the problem, we introduce the notion of an intuitionistic fuzzy recognizable step function as follows.Definition 17.
An IFSA over Σ* is called an intuitionistic fuzzy recognizable step function if there are a finite natural number n∈N, recognizable context-free languages ℒ1,…,ℒn⊆Σ*, and (ai,bi)∈(0,1]×[0,1) with 0≤ai+bi≤1 for i=1,…,n such that
(⋆)A=(μA,νA)=∐i=1n‍(ai,bi)·1ℒi,
where 1ℒi=(μ1ℒi,ν1ℒi) represents the intuitionistic characterized function of ℒi, i=1,…,n, that is,
(21)μ1ℒi(ω)={1,ifω∈ℒi0,ifω∉ℒi,ν1ℒi(ω)={0,ifω∈ℒi1,ifω∉ℒi.
And the equation (⋆) means that the following equations hold:
(22)μA(ω)=⋁i=1nai∧μ1ℒi(ω),νA(ω)=⋀i=1nbi∨ν1ℒi(ω),∀ω∈Σ*.Noting that the family of all the intuitionistic fuzzy recognizable step functions overΣ* is denoted by StepC(Σ).Proposition 18.
Letℳ1′=(Q1,Σ,Γ1,δ1,q01,Z01,F1) be an IFPDA. Then the language recognized by ℳ1′ is an intuitionistic fuzzy recognizable step function over Σ*, that is, ℒ(ℳ1′)∈ StepC(Σ).Proof.
By Proposition14, there is an IFSPDA ℳ=(Q,Σ,Γ,δ,q0,Z0,F) equivalent to ℳ1′.
LetR={(μF(q),νF(q))∣q∈Q}∖{(0,1)}={(ai,bi)∣i∈Nk}, Nk={1,…,k}. Put Fi={q∈Q∣μF(q)=ai,νF(q)=bi}, for all i∈Nk. Then we construct a PDA ℳi=(Q,Σ,Γ,δ′,q0,Z0,Fi), where the mapping δ′:Q×(Σ∪{ε})×Γ→2Q×Γ* is defined byδ′(q,τ,X)={(p,γ)∣μδ(q,τ,X,p,γ)=1,p∈Q,γ∈Γ*}, for all (q,τ,X)∈Q×(Σ∪{ε})×Γ.
Thenℒ(ℳi)=ℒi={ω∈Σ*∣(q0,ω, Z0)≻ℳi*(q,ε,γ), q∈Fi,γ∈Γ*}.
Therefore, for anyω∈Σ*, we have μℒ(ℳ1′)(ω) = μℒ(ℳ)(ω) = ⋁{μF(q)∣μ⊢ℳ*((q0,ω,Z0),(q,ε,γ)) = 1,q∈Q,γ∈Γ*}=⋁{ai∣μ⊢ℳ*((q0,ω,Z0),   (q,ε,γ))=1,μF(q) = ai,νF(q)=bi,i∈Nk,γ∈Γ*}=⋁{ai∣(q0,ω,Z0)≻ℳi*(q,ε,γ),q∈Fi,i∈Nk,γ∈Γ*}=⋁{ai∣ω∈ℒ(ℳi),i∈Nk}=⋁i∈Nkai∧μ1ℒ(ℳi)(ω), and νℒ(ℳ1′)(ω)=νℒ(ℳ)(ω)=⋀{νF(q)∣ν⊢ℳ*((q0,ω,Z0),(q,ε,γ))=0,q∈Q,γ∈Γ*}=⋀{bi∣μ⊢ℳ*((q0,ω,Z0), (q,ε,γ))=1,μF(q)=ai,νF(q)=bi,i∈Nk,γ∈Γ*}=⋀{bi∣(q0,ω,Z0)≻ℳi*(q,ε,γ),q∈Fi,i∈Nk,γ∈Γ*}=⋀{bi∣ω∈ℒ(ℳi),i∈Nk}=⋀i∈Nkbi∨ν1ℒ(ℳi)(ω).
Soℒ(ℳ)=∐i∈Nk(ai,bi)·1ℒi.Proposition18 shows that the set of the languages recognized by all the IFPDAs is a subset of StepC(Σ). In fact, StepC(Σ) is also a subset of the set of the languages recognized by all the IFPDAs. We will prove the decomposition form in the following.Theorem 19.
LetA be an IFS over Σ*. Then the following statements are equivalent:(i)
A∈ StepC(Σ);(ii)
there is an IFPDAℳ such that A=ℒ(ℳ);(iii)
there is an IFSPDAℳ such that A=ℒ(ℳ).Proof.
(i) implies (iii). SupposeA∈ StepC(Σ). Then there is a finite natural number n∈N, recognizable context-free languages ℒ1,…,ℒn⊆Σ*, and (ai,bi)∈(0,1]×[0,1) with 0≤ai+bi≤1 for i=1,…,n such that A=(μA,νA)=∐i=1n(ai,bi)·1ℒi. Let ℒi be recognized by a PDA ℳi=(Qi,Σ,Γi,δi,q0i,Z0i,Fi), and Qi∩Qj=∅ whenever i≠j, i,j∈Nn.
Next, construct an IFSPDAℳ=(Q,Σ,Γ,δ,q0,Z0,F) as follows: Q=⋃i=1nQi∪{q0}, Γ=⋃i=1nΓi∪{Z0}, where q0∉⋃i=1nQi, Z0∉⋃i=1nΓi. δ=(μδ,νδ) is an IFS over Q×(Σ∪{ε})×Γ×Q×Γ*, where the mappings μδ,νδ:Q×(Σ∪{ε})×Γ×Q×Γ*→{0,1} are defined by μδ(q0,ε,Z0,p,γ)=1 and νδ(q0,ε,Z0,p,γ)=0 if (p,γ)=(q0i,Z0i), i∈Nn; μδ(q,τ,Z,p,γ)=μδi(q,τ,Z,p,γ) and νδ(q,τ,Z,p,γ)=νδi(q,τ,Z,p,γ) if p,q∈Qi, Z∈Γi,γ∈Γi*, τ∈Σ∪{ε}, i∈Nn. Otherwise, μδ(q,τ,Z,p,γ)=0 and νδ(q,τ,Z,p,γ)=1.
F
=
(
μ
F
,
ν
F
) is an IFS in Q, where
(23)μF(q0)=⋁{ai∈[0,1]∣q0i∈Fi,i∈Nn},νF(q0)=⋀{bi∈[0,1]∣q0i∈Fi,i∈Nn},μF(q)={ai,ifq∈Fi0,ifq∉Fi∪{q0},νF(q)={bi,ifq∈Fi1,ifq∉Fi∪{q0}.
Therefore, for anyω∈Σ*, we haveμℒ(ℳ)(ω)=⋁{μ⊢ℳ*((q0,ω,Z0),(q,ε,γ))∧μF(q)∣q∈Q,γ∈Γ*},νℒ(ℳ)(ω)=⋀{ν⊢ℳ*((q0,ω,Z0),(q,ε,γ))∨νF(q)∣q∈Q,γ∈Γ*}.
Ifω=ε, then μℒ(ℳ)(ε)=(μ⊢ℳ*((q0,ε,Z0),(q0,ε,Z0))∧μF(q0))∨(⋁{μ⊢ℳ*((q0,ε,Z0),(q0i,ε,Z0i))∧μF(q0i)∣q0i∈Qi,Z0i∈Γi,i∈Nn})=μF(q0)∨(⋁{μF(q0i)∣q0i∈Qi,Z0i∈Γi,i∈Nn})=⋁{ai∈[0,1]∣q0i∈Fi,i∈Nn}=⋁i=1nai∧μ1ℒi(ε); νℒ(ℳ)(ε)=(ν⊢ℳ*((q0,ε,Z0),(q0,ε,Z0))∨νF(q0))∧(⋀{ν⊢ℳ*((q0,ε,Z0), (q0i,ε,Z0i))∨νF(q0i)∣q0i∈Qi, Z0i∈Γi,i∈Nn})=νF(q0)∧(⋀{νF(q0i)∣q0i∈Qi, Z0i∈Γi,i∈Nn})=⋀{bi∈[0,1]∣q0i∈Fi, i∈Nn}=⋀i=1nbi∨ν1ℒi(ε). If ω∈Σ*∖{ε}, then μℒ(ℳ)(ω)=⋁{μ⊢ℳ*((q0i,ω,Z0i), (q,ε,γ))∧μF(q)∣q0i∈Qi, γ∈Γ*,q∈Q,i∈Nn}=⋁{μF(q)∣q0i∈Qi, γ∈Γi*,q∈Q,i∈Nn,μ⊢ℳ*((q0i,ω,Z0i),(q,ε,γ))=1} = ⋁{ai∣q∈Fi,i∈Nn,μ⊢ℳ*((q0i,ω,Z0i),(q,ε,γ)) = 1,γ∈Γi*}=⋁{ai∣ω∈ℒi,i∈Nn}=⋁i=1nai∧μ1ℒi(ω), νℒ(ℳ)(ω)=⋀{ν⊢ℳ*((q0i,ω,Z0i), (q,ε,γ))∨νF(q)|q0i∈Qi,γ∈Γ*,q∈Q,i∈Nn} = ⋀{νF(q)∣q0i∈Qi,γ∈Γi*,q∈Q,i∈Nn, μ⊢ℳ*((q0i,ω,Z0i),(q,ε,γ))=1} = ⋀{bi∣q∈Fi,i∈Nn,μ⊢ℳ*((q0i,ω,Z0i),(q,ε,γ)) = 1,γ∈Γi*}=⋀{bi∣ω∈ℒi,i∈Nn} = ⋀i=1nai∨ν1ℒi(ω).
(iii) implies (ii): obviously.
(ii) implies (i): it is concluded by Proposition18.Next, we will discuss the characterization ofIFPDA∅.Proposition 20.
Letℳ=(Q,Σ,Γ,δ,q0,Z0,∅) be an IFPDA∅. Then there is a special IFPDA∅ℳ′=(Q′,Σ,Γ′,δ′,q0′,X0,∅) equivalent to ℳ.Proof.
Givenℳ, we construct an IFPDA∅ℳ′=(Q′,Σ,Γ′,δ′,q0′,X0,∅) as follows:(1)
Q′=Q2×(L1∖{0})×(L2∖{1}), where Q2=Q∪{p0}, Γ′=Γ∪{X0}, L1=X∧, L2=Y∨, X=Im(μδ), Y=Im(νδ), and q0′=(p0,1,0);(2)
δ′=(μδ′,νδ′) is an IFS in Q′×(Σ∪{ε})×Γ′×Q′×Γ′*, where the mappings μδ′,νδ′:Q′×(Σ∪{ε})×Γ′×Q′×Γ′*→[0,1] are defined by
(i)
μδ′((p0,1,0),ε,X0,(q0,1,0),Z0X0)=1, νδ′((p0,1,0),ε,X0,(q0,1,0),Z0X0)=0;(ii)
μδ′((q,a,b),τ,X,(q′,a∧a′,b∨b′),γ)=1 and νδ′((q,a,b),τ,X,(q′,a∧a′,b∨b′),γ)=0 whenever μδ(q,τ,X,q′,γ)=a′>0 and νδ(q,τ,X,q′,γ)=b′<1, for all (q,a,b)∈Q′, τ∈Σ∪{ε}, X∈Γ, γ∈Γ*;(iii)
if0≤a+b≤1, then μδ′((q,a,b), ε,X0, (q,a,b),ε)=a and νδ′((q,a,b), ε,X0, (q,a,b),ε)=b. If a+b>1, then μδ′((q,a,b),ε,X0,(q,a,b),ε)=0 and νδ′((q,a,b),ε,X0,(q,a,b),ε)=1;(iv)
In other cases,μδ′((q,a,b),τ,X, (p,c,d),γ)=0 and νδ′((q,a,b),τ, X,(p,c,d),γ)=1.
Obviously,δ′=(μδ′,νδ′) is a finite IFS in Q′×(Σ∪{ε})×Γ′×Q′×Γ′*.
Next, we showℒ(ℳ′)=ℒ(ℳ).
Firstly let us show that, for anyω=τ1⋯τn∈Σ*, τi∈Σ∪{ε}, i∈{1,…,n}, qn∈Q,
(24)μ⊢ℳ′*((q0′,ω,X0),((qn,an,bn),ε,X0))={1,if(P2)is satisfied0,otherwise,ν⊢ℳ′*((q0′,ω,X0),((qn,an,bn),ε,X0))={0,if(P2)is satisfied1,otherwise,
where the condition (P2) is the following:(P2)
there existq1,…,qn-1∈Q, Z1,…,Zn-1∈Γ, γ1,…,γn-1∈Γ*, s.t. an=μ⊢ℳ((q0,ω,Z0), (q1,τ2⋯τn,Z1γ1))∧μ⊢ℳ((q1, τ2⋯τn,Z1γ1), (q2,τ3⋯τn,Z2γ2))∧⋯∧μ⊢ℳ((qn-1, τn,Zn-1γn-1), (qn,ε,ε))>0 and bn=ν⊢ℳ((q0,ω,Z0), (q1,τ2⋯τn,Z1γ1))∨ν⊢ℳ((q1,τ2⋯τn,Z1γ1), (q2,τ3⋯τn,Z2γ2))∨⋯∨ν⊢ℳ((qn-1, τn,Zn-1γn-1), (qn,ε,ε))<1.
In fact, if(P2) is satisfied, then let μ⊢ℳ((qi,τi+1⋯τn,Ziγi),(qi+1,τi+2⋯τn,Zi+1γi+1))=ci, ν⊢ℳ((qi,τi+1⋯τn,Ziγi),(qi+1,τi+2⋯τn,Zi+1γi+1))=di, i=0,1,…,n-2, where γ0=ε. We have μ⊢ℳ′((q0,1,0), ω,Z0X0), ((q1,c0,d0), τ2⋯τn, Z1γ1X0)) = 1,ν⊢ℳ′((q0,1,0), ω,Z0X0), ((q1,c0,d0), τ2⋯τn,Z1γ1X0)) = 0,μ⊢ℳ′(((q1,c0,d0), τ2⋯τn,Z1γ1X0), ((q2,c0∧c1,d0∨d1), τ3⋯τn,Z2γ2X0)) = 1,ν⊢ℳ′(((q1,c0,d0),τ2⋯τn,Z1γ1X0), ((q2,c0∧c1,d0∨d1), τ3⋯τn,Z2γ2X0)) = 0,⋮μ⊢ℳ′(((qn-1, c0∧c1∧⋯∧cn-2, d0∨d1∨⋯∨dn-2), τn,Zn-1γn-1X0), ((qn,an,bn), ε,X0))=1,ν⊢ℳ′(((qn-1,c0∧c1∧⋯∧cn-2, d0∨d1∨⋯∨dn-2), τn,Zn-1γn-1X0), ((qn,an,bn),ε,X0))=0.
Henceμ⊢ℳ′*((q0′,ω,X0), ((qn,an,bn), ε,X0)≥μ⊢ℳ′((q0,1,0), ω,Z0X0), ((q1,c0,d0), τ2⋯τn, Z1γ1X0))∧μ⊢ℳ′(((q1, c0,d0), τ2⋯τn,Z1γ1X0), ((q2,c0∧c1,d0∨d1), τ3⋯τn, Z2γ2X0))∧⋯∧μ⊢ℳ′(((qn-1, c0∧c1∧⋯∧cn-2, d0∨d1∨⋯∨dn-2), τn,Zn-1γn-1X0), ((qn,an,bn),ε,X0))=1, ν⊢ℳ′*((q0′,ω,X0), ((qn,an,bn),ε,X0))≤ν⊢ℳ′((q0,1,0), ω,Z0X0),((q1,c0,d0), τ2⋯τn,Z1γ1X0))∨ν⊢ℳ′(((q1,c0, d0),τ2⋯τn,Z1γ1X0), ((q2,c0∧c1,d0∨d1), τ3⋯τn,Z2γ2X0))∨⋯∨ν⊢ℳ′(((qn-1, c0∧c1∧⋯∧cn-2, d0∨d1∨⋯∨dn-2), τn,Zn-1γn-1X0), ((qn,an,bn),ε,X0)) = 0.
Sinceμ⊢ℳ′*((q0′,ω,X0), ((qn,an, bn), ε, X0))≤1 and ν⊢ℳ′*((q0′,ω, X0), ((qn,an, bn),ε,X0))≥0, μ⊢ℳ′*((q0′, ω,X0), ((qn,an, bn), ε,X0))=1 and ν⊢ℳ′*((q0′,ω, X0), ((qn,an,bn), ε,X0))=0.
If(P2) is not satisfied, then we assume μ⊢ℳ′*((q0′,ω,X0),((qn,an,bn), ε,X0))>0.
So there at least existq1,…,qn-1∈Q, Z1,…,Zn-1∈Γ, γ1,…,γn-1∈Γ*, s.t. μ⊢ℳ′((q0,1,0),ω,Z0X0), ((q1,c0,d0), τ2⋯τn,Z1γ1X0))∧μ⊢ℳ′(((q1, c0,d0), τ2⋯τn, Z1γ1X0), ((q2,c0∧c1, d0∨d1), τ3⋯τn,Z2γ2X0))∧⋯∧μ⊢ℳ′(((qn-1, c0∧c1∧⋯∧cn-2, d0∨d1∨⋯∨dn-2),τn,Zn-1γn-1X0), ((qn,an,bn),ε,X0))>0.
Hencean=μ⊢ℳ((q0,ω,Z0), (q1,τ2⋯τn,Z1γ1))∧μ⊢ℳ((q1, τ2⋯τn,Z1γ1), (q2,τ3⋯τn, Z2γ2))∧⋯∧μ⊢ℳ((qn-1, τn,Zn-1γn-1), (qn,ε,ε))>0 and bn=ν⊢ℳ((q0,ω,Z0), (q1,τ2⋯τn,Z1γ1))∨ν⊢ℳ((q1, τ2⋯τn,Z1γ1), (q2,τ3⋯τn, Z2γ2))∨⋯∨ν⊢ℳ((qn-1, τn,Zn-1γn-1), (qn,ε,ε))<1.
It contradicts with the assumption. Soμ⊢ℳ′*((q0′,ω,X0), ((qn,an,bn),ε,X0)=0 if (P2) is not satisfied. In a similar way, it is easily concluded that ν⊢ℳ′*((q0′,ω,X0),((qn,an,bn),ε,X0)=1 if (P2) is not satisfied.
Secondly, for anyω=τ1⋯τn∈Σ*, τi∈Σ∪{ε}, i∈{1,…,n}, μℒ(ℳ′)(ω) = ⋁{μ⊢ℳ′*((q0′,ω,X0), ((qn,an,bn), ε,X0))∧μ⊢ℳ′((qn,an,bn), ε,X0),((qn,an,bn),ε,ε))∣(qn,an,bn)∈Q′} = ⋁{μ⊢ℳ((q0,ω,Z0),(q1,τ2⋯τn, Z1γ1))∧μ⊢ℳ((q1,τ2⋯τn,Z1γ1), (q2,τ3⋯τn,Z2γ2))∧⋯∧μ⊢ℳ((qn-1, τn,Zn-1γn-1),(qn,ε,ε))∣q1,…,qn∈Q,Z1,…,Zn-1∈Γ, γ1,…,γn-1∈Γ*} = μℒ(ℳ)(ω).
Similarly,νℒ(ℳ′)(ω)=νℒ(ℳ)(ω).
Henceℒ(ℳ′)=ℒ(ℳ).Remark 21.
Proposition20 presents an equivalence of an IFPDA∅. In particular, due to the underlying truth-valued domain being an IFS, the proof technique used in Proposition 20 is to some extent different from the technique of extended subset construction in [33]. Moreover, Proposition 20 plays an important role in proving the fact that any language recognized by an IFPDA∅ is an intuitionistic fuzzy recognizable step function.Proposition 22.
Letℳ=(Q,Σ,Γ,δ,q0,Z0,∅) be an IFPDA∅. Then the language recognized by ℳ is an intuitionistic fuzzy recognizable step function over Σ*, that is, ℒ(ℳ)∈ StepC(Σ).Proof.
Letℳ=(Q,Σ,Γ,δ,q0,Z0,∅) be an IFPDA∅. Then there is a special IFPDA∅ℳ′=(Q′,Σ,Γ′,δ′,q0′,X0,∅) constructed by Proposition 20, which is equivalent to ℳ. For any (a,b)∈(L1∖{0})×(L2∖{1}) with 0<a+b≤1, construct a classical PDA with empty stack ℳab=(Q′,Σ,Γ′,δab′′,q0′,X0,∅), where Q′,Σ,Γ′,q0′, and X0 are the same as those in ℳ′, and the function δab′′:Q′×Σ×Γ′→2Q′×Γ′* is defined by(i)
δab′′((p0,1,0),ε,X0)={((q0,1,0),Z0X0)};(ii)
δab′′((q,c,d),τ,X)={((q′,c∧c1,d∨d1),γ)∣c1=μδ(q,τ,X,q′,γ)>0,d1=νδ(q,τ,X,q′, γ)<1,q′∈Q,γ∈Γ*};(iii)
δab′′((q,a,b),ε,X0)={((q,a,b),ε)};(iv)
δab′′((q,c,d),τ,X)=∅ in other cases.
Then for anyω∈Σ*, we have μℒ(ℳ)(ω) = μℒ(ℳ′)(ω) = ⋁{μ⊢ℳ′*((q0′,ω, X0), ((qn,an, bn), ε,X0))∧μ⊢ℳ′((qn, an,bn), ε,X0),((qn,an,bn), ε,ε))∣(qn,an,bn)∈Q′}=⋁{an∣(qn,an,bn)∈Q′, 0<an+bn≤1, μ⊢ℳ′*((q0′,ω,X0),((qn,an,bn), ε,X0))=1} = ⋁{an∣(q0′,ω,X0)≻ℳab*((qn, an,bn),ε,ε), qn∈Q} = ⋁a∈L1∖{0}a∧μ1ℒ(ℳab)(ω), and νℒ(ℳ)(ω)=νℒ(ℳ′)(ω) = ⋀{ν⊢ℳ′*((q0′,ω,X0), ((q,a,b), ε,X0))∨ν⊢ℳ′((q, a,b), ε,X0),((q,a,b), ε,ε))∣(q,a, b)∈Q′} = ⋀{b∣(q,a,b)∈Q′, 0<a + b≤1,μ⊢ℳ′*((q0′,ω,X0), ((q,a,b),ε,X0)) = 1}=⋀{b∣(q0′,ω,X0)≻ℳab*((q, a,b),ε,X0), (q,a,b)∈Q′} = ⋀b∈L2∖{1}b∨ν1ℒ(ℳab)(ω).
Thereforeℒ(ℳ)∈ StepC(Σ).Theorem 23.
LetA be an IFS over Σ*. Then the following statements are equivalent:(1)
A∈StepC(Σ);(2)
A is accepted by a certain IFPDA∅ℳ.Proof.
(i) implies (ii). SupposeA∈ StepC(Σ). Then there are a finite natural number n∈N, recognizable context-free languages ℒ1,…,ℒn⊆Σ*, and (ai,bi)∈(0,1]×[0,1) with 0≤ai+bi≤1 for i=1,…,n such that A=(μA,νA)=∐i=1n(ai,bi)·1ℒi. Let ℒi be recognized by PDA ℳi=(Qi,Σ,Γi,δi,q0i,Z0i,∅), and Qi∩Qj=∅ whenever i≠j, i,j∈Nn.
Next, construct an IFPDA∅ℳ=(Q,Σ,Γ,δ,I,Z0,∅) as follows: Q=⋃i=1nQi, Γ=⋃i=1nΓi∪{Z0}, and I=(μI,νI) are an IFS over Q, defined by μI(q0i)=ai, νI(q0i)=bi, i∈Nn; otherwise μI(q)=0 and νI(q)=1. δ=(μδ,νδ) is an IFS over Q×(Σ∪{ε})×Γ×Q×Γ*, where the mappings μδ,νδ:Q×(Σ∪{ε})×Γ×Q×Γ*→{0,1} are defined by μδ(q0i,ε,Z0,q0i,Z0i)=1 and νδ(q0i,ε,Z0,q0i,Z0i)=0, i∈Nn; μδ(q,τ,Z,p,γ)=1 and νδ(q,τ,Z,p,γ)=0 if p,q∈Qi, Z∈Γi,γ∈Γi*, τ∈Σ, i∈Nn and (p,γ)∈δ(q,τ,Z). Otherwise, μδ(q,τ,Z,p,γ)=0 and νδ(q,τ,Z,p,γ)=1.
ThenA=ℒ(ℳ)=∐i=1n(ai,bi)·1ℒi.
(ii) implies (i). It is concluded by Proposition22.One can see that IFPDAs and IFPDAs∅ are equivalent to a type of intuitionistic fuzzy recognizable step functions over a set, respectively, by Theorems 19 and 23. Therefore, IFPDAs and IFPDAs∅ are equivalent in the sense that they accept or recognize the same classes of intuitionistic fuzzy languages. That is to say, the following statement is true.Corollary 24.
For any IFPDAℳ, there is an IFPDA∅ℳ′ equivalent to ℳ. For any IFPDA∅ℳ′, there is an IFPDA ℳ equivalent to ℳ′.


## 4. Intuitionistic Fuzzy Context-Free Grammars

As a type of generator of intuitionistic fuzzy context-free languages, the notion of intuitionistic fuzzy context-free grammars is introduced in the section. Then the relationship between intuitionistic fuzzy context-free grammars, IFPDAs, IFPDAs∅, and intuitionistic fuzzy recognizable step functions is discussed. The algebraic properties of intuitionistic fuzzy context-free languages are investigated finally.Definition 25.
An intuitionistic fuzzy grammar is a systemG=(N,T,P,I), where(i)
N is a finite nonempty alphabet of variables;(ii)
T is a finite nonempty alphabet of terminals and T∩N=∅;(iii)
I is an intuitionistic fuzzy set over N;(iv)
P is a finite collection of productions over T∪N, and P={x→y∣x∈(N∪T)*N(N∪T)*, y∈(N∪T)*, μρ(x→y)>0,νρ(x→y)<1},where ρ=(μρ,νρ) is an IFS over (N∪T)*×(N∪T)*, μρ(x,y), and νρ(x,y) mean the membership degree and the nonmembership degree that x will be replaced by y, respectively, denoted by μρ(x,y)=μρ(x→y), νρ(x,y)=νρ(x→y).Forα,β∈(N∪T)*, if x→y∈P, then αyβ is said to be directly derivable from αxβ, denoted by αxβ⇒αyβ, and define μρ(αxβ⇒αyβ)=μρ(x→y), νρ(αxβ⇒αyβ)=νρ(x→y).Ifα1,…,αm are strings in (N∪T)* and α1→α2,…,αm-1→αm∈P, then α1 is said to derive αm in G, or, equivalently, αm is derivable from α1 in G. This is expressed by α1⇒G*αm or simply α1⇒*αm. The expression α1→α2→⋯→αm is referred to as a derivation chain from α1 to αm.An intuitionistic fuzzy grammarG generates an intuitionistic fuzzy language ℒ(G)=(μG,νG) in the following manner. For any θ=ωn∈T*, n≥1, μG(θ)=⋁{μI(ω0)∧μρ(ω0⇒ω1)∧⋯∧μρ(ωn-1⇒ωn)∣ω0∈N,ω1,…,ωn-1∈(N∪T)*}, and νG(θ)=⋀{νI(ω0)∨νρ(ω0⇒ω1)∨⋯∨νρ(ωn-1⇒ωn)∣ω0∈N,ω1,…,ωn-1∈(N∪T)*}.μ
G
(
θ
) and νG(θ) express the membership and nonmembership degree of θ in the language generated by grammar G, respectively. Obviously, ℒ(G)=(μG,νG) is well defined. In fact, for any θ=ωn∈T*, n≥1, there is the strongest derivation from ω0 to ωn, that is, ω0⇒ω1′⇒⋯⇒ωn-1′⇒ωn, such that μG(θ)=μI(ω0)∧μρ(ω0⇒ω1′)∧⋯∧μρ(ωn-1′⇒ωn). So νG(θ)≤νI(ω0)∨νρ(ω0⇒ω1′)∨⋯∨νρ(ωn-1′⇒ωn), and μG(θ)+νG(θ)≤μG(θ)+νI(ω0)∨νρ(ω0⇒ω1′)∨⋯∨νρ(ωn-1′⇒ωn)=(μG(θ)+νI(ω0))∨(μG(θ)+νρ(ω0⇒ω1′))∨⋯∨(μG(θ)+νρ(ωn-1′⇒ωn))≤(μI(ω0)+νI(ω0))∨(μρ(ω0⇒ω1′)+νρ(ω0⇒ω1′))∨⋯∨(μρ(ωn-1′⇒ωn)+νρ(ωn-1′⇒ωn))≤1.For any intuitionistic fuzzy grammarsG1 and G2, if ℒ(G1)=ℒ(G2) in the sense of equality of intuitionistic fuzzy sets, then the grammars G1 and G2 are said to be equivalent.For any intuitionistic fuzzy grammarG=(N,T,P,I), if Im(I)=Im(μI)∪Im(νI)={0,1} and supp(I)={S}, then G is also written as G=(N,T,P,S).Proposition 26.
LetA be an IFS over T*. Then the following statements are equivalent:(i)
A is generated by a certain intuitionistic fuzzy grammar G=(N,T,P,I);(ii)
A is generated by a certain intuitionistic fuzzy grammar G=(N′,T′,P′,S).Proof.
(i) implies (ii). LetA be generated by an intuitionistic fuzzy grammar G=(N,T,P,I). Then we construct an intuitionistic fuzzy grammar G′=(N′,T′,P′,S) as follows: N′=N∪{S}, S∉N; T′=T, P′=P∪P1, where P1={S→q∣q∈ supp(I), μρ(S→q)=μI(q),νρ(S→q)=νI(q)}.
Next we show thatℒ(G′)=ℒ(G). In fact, G′=(N′,T′,P′,I′), where I′ is an IFS over N′, μI′(S)=1, νI′(S)=0; μI′(q)=0 and νI′(q)=1 when q∈N.
For anyθ=ωn∈T*, n≥1, μG′(θ)=⋁{μI′(ω0)∧μρ(ω0⇒ω1)∧⋯∧μρ(ωn-1⇒ωn)∣ω0∈N′,ω1,…,ωn-1∈(N′∪T′)*}=⋁{μρ(S⇒ω1)∧μρ(ω1⇒ω2)∧⋯∧μρ(ωn-1⇒ωn)∣ω1,…,ωn-1∈(N′∪T′)*}=⋁{μρ(S⇒q)∧μρ(q⇒ω2)∧⋯∧μρ(ωn-1⇒ωn)∣q∈N,ω2,…,ωn-1∈(N∪T)*}=⋁{μI(q)∧μρ(q⇒ω2)∧⋯∧μρ(ωn-1⇒ωn)∣q∈N,ω2,…,ωn-1∈(N∪T)*}=μG(θ) and νG′(θ)=⋀{νI′(ω0)∨νρ(ω0⇒ω1)∨⋯∨νρ(ωn-1⇒ωn)∣ω0∈N′,ω1,…,ωn-1∈(N′∪T′)*}=⋀{νρ(S⇒ω1)∨νρ(ω1⇒ω2)∨⋯∨νρ(ωn-1⇒ωn)∣ω1,…,ωn-1∈(N′∪T′)*}=⋀{νρ(S⇒q)∨νρ(q⇒ω2)∨⋯∨νρ(ωn-1⇒ωn)∣q∈N,ω2,…,ωn-1∈(N∪T)*}=⋀{νI(q)∨νρ(q⇒ω2)∨⋯∨νρ(ωn-1⇒ωn)∣q∈N,ω2,…,ωn-1∈(N∪T)*}=νG(θ).
Henceℒ(G′)=ℒ(G).
(ii) implies (i), obviously.Definition 27.
(1) An intuitionistic fuzzy grammarG=(N,T,P,I) is called context-free (IFCFG, for short) if it has only productions of the form A→ω∈P with A∈N and ω∈(N∪T)*. And the language ℒ(G), generated by the IFCFG G, is said to be an intuitionistic fuzzy context-free language (IFCFL).
(2) An IFCFGG=(N,T,P,S) is called an intuitionistic fuzzy Chomsky normal form (IFCNF) if it has only productions of the form A→BC∈P or A→a∈P or S→ε, where A,B,C∈N, B≠S, C≠S and a∈T. (3) An IFCFG G=(N,T,P,S) is called an intuitionistic fuzzy Greibach normal form (IFGNF) if all the productions are of the form A→ax∈P or S→ε, where A∈N, a∈T, and x∈(N∖{S})*. (4) An IFCFG G=(N,T,P,I) is called a simple-typed intuitionistic fuzzy context-free grammar (IFSCFG) if
(25)P={A⟶x∣A∈N,x∈(N∪T)*,μρ(A⟶x)=1}.Proposition 28.
LetG=(N,T,P,I) be an IFCFG and ℒ(G)=(μG,νG) be the intuitionistic fuzzy context-free language generated by G. Then the image set of ℒ(G) is a finite subset of the unit interval [0,1].Proof.
LetG=(N,T,P,I) be an IFCFG. Then Im(μρ) and Im(νρ) are finite. For any θ=ωn∈T*, n≥1, there exist natural numbers d,l such that μG(θ)=⋁{μI(S)∧μρ(S⇒ω1)∧μρ(ω1⇒ω2)∧⋯∧μρ(ωn-1⇒ωn)∣S∈N,ω1,…,ωn-1∈(N∪T)*}=(a10∧⋯∧a1n-1∧a1n)∨⋯∨(ad0∧⋯∧adn-1∧adn) and νG(θ)=⋀{νI(S)∨νρ(S⇒ω1)∨νρ(ω1⇒ω2)∨⋯∨νρ(ωn-1⇒ωn)∣S∈N,ω1,…,ωn-1∈(N∪T)*}=(b10∨⋯∨b1n-1∨b1n)∧⋯∧(bl0∨⋯∨bln-1∨bln), where aik∈Im(μI)∪Im(μρ), bjk∈Im(νI)∪Im(νρ), i∈{1,…,d}, j∈{1,…,l}, k∈{0,1,…,n}. Let X=Im(μI)∪Im(μρ) and Y=Im(νI)∪Im(νρ). Then X and Y are finite subsets of the interval [0,1]. (X∧)∨ and (Y∨)∧ are also finite by Lemma 8. Since μG(θ)∈(X∧)∨ and νG(θ)∈(Y∨)∧ for any θ∈T*, we have Im(μG)⊆(X∧)∨ and Im(νG)⊆(Y∨)∧. Hence Im(ℒ(G))=Im(μG)∪Im(νG) is finite.Proposition 29.
LetG=(N,T,P,S) be an IFCFG. Then ℒ(G)∈ StepC(T).Proof.
LetX=Im(μρ) and Y=Im(νρ). Then X and Y have finite elements because P is a finite collection of productions over T∪N. Suppose L1=X∧ and L2=Y∨. Then L1 and L2 are finite by Lemma 8. For any (a,b)∈(L1∖{0})×(L2∖{1}), 0≤a+b≤1, we construct a classical context-free grammar Gab=(N′,T,Pab′,S′) as follows:
N
′
=
N
×
(
L
1
∖
{
0
}
)
×
(
L
2
∖
{
1
}
), S′=(S,1,0)∈N′, Pab′ consists of the form:(1)
(A,a1,b1)→D1⋯Dk whenever μρ(A→τ1⋯τk)>0 and νρ(A→τ1⋯τk)<1, where
(26)Di={(τi,a2,b2),ifτi∈Nτi,ifτi∈Ti=1,…,k; a2=a1∧μρ(A→τ1⋯τk) and b2=b1∨νρ(A→τ1⋯τk);(2)
(A,a1,b1)→x whenever a≤a1∧μρ(A→x) and b≥b1∨νρ(A→x), for all A∈N,x∈(N∪T)*.
Thenℒ(Gab)={ω∈T*∣S′⇒Gab*ω}={ω∈T*∣a≤μρ(S⇒u1)∧μρ(u1⇒u2)∧⋯∧μρ(un-1⇒ω),b≥νρ(S⇒u1)∨νρ(u1⇒u2)∨⋯∨νρ(un-1⇒ω),u1,…,un-1∈(N∪T)*}.
Next it suffices to show thatℒ(G)=∐‍(a,b)·1ℒ(Gab), that is, μG(ω)=⋁a∈L1∖{0}a∧μ1ℒ(Gab)(ω) and νG(ω)=⋀b∈L2∖{1}b∨ν1ℒ(Gab)(ω), for all ω∈T*.
SupposeμG(ω)=ak>0. Then there exist u1′,…,un-1′∈(N∪T)* such that ak=μρ(S⇒u1′)∧μρ(u1′⇒u2′)∧⋯∧μρ(un-1′⇒ω). Put c=νρ(S⇒u1′)∨νρ(u1′⇒u2′)∨⋯∨νρ(un-1′⇒ω). Then c<1 and ω∈ℒ(Gkc). Therefore, μG(ω)≤⋁a∈L1∖{0}a∧μ1ℒ(Gab)(ω) and νG(ω)≥⋀b∈L2∖{1}b∨ν1ℒ(Gab)(ω) for any ω∈T*. In addition, ⋁a∈L1∖{0}a∧μ1ℒ(Gab)(ω)=⋁{a∈L1∖{0}∣ω∈ℒ(Gab)}≤⋁{μρ(S⇒u1)∧μρ(u1⇒u2)∧⋯∧μρ(un-1⇒ω)∣ω∈ℒ(Gab),u1,…,un-1∈(N∪T)*}≤⋁{μρ(S⇒u1)∧μρ(u1⇒u2)∧⋯∧μρ(un-1⇒ω)∣u1,…,un-1∈(N∪T)*}=μG(ω), νG(ω)=⋀{νρ(S⇒u1)∨νρ(u1⇒u2)∨⋯∨νρ(un-1⇒ω)∣u1,…,un-1∈(N∪T)*}≤⋀{b∈L2∖{1}∣b≥νρ(S⇒u1)∨νρ(u1⇒u2)∨⋯∨νρ(un-1⇒ω),u1,…,un-1∈(N∪T)*}≤⋀{b∈L2∖{1}∣b≥νρ(S⇒u1)∨νρ(u1⇒u2)∨⋯∨νρ(un-1⇒ω),a≤μρ(S⇒u1)∧μρ(u1⇒u2)∧⋯∧μρ(un-1⇒ω),u1,…,un-1∈(N∪T)*}=⋀{b∈L2∖{1}∣ω∈ℒ(Gab)}=⋀b∈L2∖{1}b∨ν1ℒ(Gab)(ω).
It is concluded thatμG(ω)=⋁a∈L1∖{0}a∧μ1ℒ(Gab)(ω) and νG(ω)=⋀b∈L2∖{1}b∨ν1ℒ(Gab)(ω), for all ω∈T*.Proposition29 states that any language recognized by an IFCFG is an intuitionistic fuzzy recognizable step function, where the proof technique is constructive. Next we will show that the set consisting of all the intuitionistic fuzzy recognizable step functions coincides with that of languages recognized by IFCFGs.Theorem 30.
LetA be an IFS over T*. Then the following statements are equivalent:(1)
A∈ StepC(T);(2)
There is an IFCFGG such that A=ℒ(G);(3)
There is an IFSCFGG such that A=ℒ(G).Proof.
(1) implies (3). LetA=∐i=1k(ai,bi)·1ℒi, where ai,bi∈[0,1], ai+bi≤1, i∈Nk, and ℒ1,…,ℒk⊂T* are classical context-free languages. Suppose ℒi is generated by a context-free grammar Gi=(Ni,T,Pi,S0i) and Ni∩Nj=∅ whenever i≠j. Then we construct an IFSCFG G=(N,T,P,I) as follows: N=⋃i=1kNi, P=⋃i=1kPi, I=(μI,νI) is an IFS over N, where the mappings μI,νI:N→[0,1] are defined by μI(S0i)=ai, νI(S0i)=bi; μI(q)=0 and νI(q)=1 whenever q∈N∖{S0i∣i=1,…,k}.
Next, we showA=ℒ(G)=∐i=1k(ai,bi)·1ℒi. In fact, for any ω=un∈T*, μG(ω)=⋁{μI(S)∧μρ(S⇒u1)∧μρ(u1⇒u2)∧⋯∧μρ(un-1⇒ω)∣S∈N,u1,…,un-1∈(N∪T)*}=⋁{μI(S0i)∣S0i⇒Gi*ω,S0i∈N,i∈Nk}=⋁{ai∣ω∈ℒi,i∈Nk}=⋁i=1kai∧μ1ℒi(ω) and νG(ω)=⋀{νI(S)∨νρ(S⇒u1)∨νρ(u1⇒u2)∨⋯∨νρ(un-1⇒ω)∣S∈N,u1,…,un-1∈(N∪T)*}=⋀{νI(S0i)∣S0i⇒Gi*ω,S0i∈N,i∈Nk}=⋀{bi∣ω∈ℒi,i∈Nk}=⋀i=1kbi∨ν1ℒi(ω).
Henceℒ(G)=(μG,νG)=∐i=1k(ai,bi)·1ℒi=A.
(3) implies (2). It is true obviously since an IFSCFG is a special IFCFG by Definition27.
(2) implies (1). It is straightforward by Propositions26 and 29.Theorem 31.
LetA be an IFS over Σ*. Then the following statements are equivalent:(1)
A∈ StepC(Σ);(2)
there is an IFPDAℳ such that A=ℒ(ℳ);(3)
there is an IFPDA∅ℳ such that A=ℒ(ℳ);(4)
there is an IFCFGG such that A=ℒ(G);(5)
there is an IFCNFG such that A=ℒ(G);(6)
there is an IFGNFG such that A=ℒ(G).Proof.
(1) implies (5). LetA∈ StepC(Σ). Then suppose A=∐i=1k(ai,bi)·1ℒi, where ai,bi∈[0,1], ai+bi≤1, i∈Nk, and ℒ1,…,ℒk⊂Σ* are classical context-free languages.
If supp(A)={ε}, then we construct an IFCNF G=(N,Σ,P,S) as follows: N={S}, P={S→ε∣μρ(S→ε)=μA(ε),νρ(S→ε)=μA(ε)}. Clearly, ℒ(G)=A.
If supp(A)∖{ε}≠∅, then there is a Chomsky normal form grammar Gi=(Ni,Σ,Pi,S0i) such that ℒ(Gi)=ℒi∖{ε}, for any ℒi with ℒi∖{ε}≠∅, i=1,…,k. Let Ni∩Nj=∅ whenever i≠j. Then we construct an IFSCFG G=(N,Σ,P,I) according to the method constructed by Theorem 30, where N=⋃i=1kNi, P=⋃i=1kPi, I=(μI,νI) is an IFS over N, and the mappings μI,νI:N→[0,1] are defined by μI(S0i)=ai, νI(S0i)=bi; μI(q)=0 and νI(q)=1 whenever q∈N∖{S0i∣i=1,…,k}. Next, we construct an IFCNF G′=(N′,Σ,P′,S) as follows:(i)
N′=N∪{S}, S∉N;(ii)
P′=P∪P′′, where P′′ has the productions in the form of
(E1)
S→ε with μρ(S→ε)=μA(ε),νρ(S→ε)=μA(ε) whenever ε∈ supp(A);(E2)
S→BC with μρ(S→BC)=μI(S0i) and νρ(S→BC)=νI(S0i) whenever S0i∈ supp(I) and S0i→BC∈Pi, i=1,…,k;(E3)
S→α with μρ(S→α)=⋁{μI(S0i)∣S0i∈ supp(I), S0i→α∈Pi,i=1,…,k} and νρ(S→α)=⋀{νI(S0i)∣S0i∈ supp(I), S0i→α∈Pi,i=1,…,k} whenever S0i∈ supp(I) and S0i→α∈Pi,i=1,…,k.
Then we haveℒ(G′)=(μG′,νG′)=A. In fact, for any ω∈Σ*, if ω=ε, then μG′(ε)=μρ(S→ε)=μA(ε) and νG′(ε)=νρ(S→ε)=νA(ε); if ω≠ε, then μG′(ω)=⋁{μρ(S⇒G′u1)∧μρ(u1⇒G′u2)∧⋯∧μρ(un-1⇒G′ω)∣u1,u2,…,un-1∈(N′∪Σ)*}=⋁{μI(S0i)∧μρ(S0i⇒Giu1)∧μρ(u1⇒Giu2)∧⋯∧μρ(un-1⇒Giω)∣u1,u2,…,un-1∈(N∪Σ)*,i∈Nk}=⋁{ai∣ω∈ℒ(Gi),i∈Nk}=⋁i=1kai∧μ1ℒi(ω) and νG′(ω)=⋀{νρ(S⇒G′u1)∨νρ(u1⇒G′u2)∨⋯∨νρ(un-1⇒G′ω)∣u1,u2,…,un-1∈(N′∪Σ)*}=⋀{νI(S0i)∨νρ(S0i⇒Giu1)∨νρ(u1⇒Giu2)∨⋯∨νρ(un-1⇒Giω)∣u1,u2,…,un-1∈(N∪Σ)*,i∈Nk}=⋀{ai∣ω∈ℒ(Gi),i∈Nk}=⋀i=1kai∨μ1ℒi(ω).
(1) implies (6), similarly. The proof is omitted.
(5) implies (4), (6) implies (4), obviously, since IFCNF and IFGNF are special IFCFGs respectively.
(1), (2), (3), and (4) are equivalent mutually by Theorems19, 23, and 30.
Theorem31 states that IFCFLs, the set of intuitionistic fuzzy languages recognized by IFPDA and the set of intuitionistic fuzzy recognizable step functions, coincide with each other. Next we discuss some operations on the family of IFCFLs.
LetA=(μA,νA) and B=(μB,νB) be IFSs over Σ*, λ,θ∈[0,1], and 0≤λ+θ≤1. Then the operations of union, scalar product, reversal, concatenation and Kleene closure are defined, respectively, by(i)
A∪B=(μA∪B,νA∪B), μA∪B(ω)=μA(ω)∨μB(ω),νA∪B(ω)=νA(ω)∧νB(ω);(ii)
(λ,θ)A=(λ∧μA,θ∨νA), (λ∧μA)(ω)=λ∧μA(ω), (θ∨νA)(ω)=θ∨νA(ω);(iii)
A-1=(μA-1,νA-1), μA-1(ω)=μA(ω-1), νA-1(ω)=νA(ω-1);(iv)
AB=(μAB,νAB), μAB(ω)=⋁{μA(ω1)∧μB(ω2)∣ω1ω2=ω}, νAB(ω)=⋀{νA(ω1)∨νB(ω2)∣ω1ω2=ω};(v)
A*=(μA*,νA*), μA*(ω)=⋁{μA(ω1)∧⋯∧μA(ωk):k≥1,ω=ω1⋯ωk}, νA*(ω)=⋀{νA(ω1)∨⋯∨νA(ωk):k≥1,ω=ω1⋯ωk} for any ω∈Σ*, where ω-1 represents the reversal of ω, that is, if ω=ω1⋯ωk, then ω-1=ωk⋯ω1, for all ω∈Σ*.Theorem 32.
(1) The family StepC(Σ) is closed under the operations of union, scalar product, reversal, concatenation, and Kleene closure. That is, A∪B, (λ,θ)A, A-1, AB, A*∈ StepC(Σ), for any A,B∈ StepC(Σ), λ,θ∈[0,1], 0≤λ+θ≤1.
(2) Leth:Σ1*→Σ2* be a homomorphism. If A∈ StepC(Σ2), then h-1(A)=A∘h∈ StepC(Σ1). (3) Let h:Σ1*→Σ2* be a homomorphism. If h satisfies, for τ∈Σ, h(τ)≠ε, and g=(μg,νg)∈ StepC(Σ1), then h(g)=(μh(g),νh(g))∈ StepC(Σ2), where μh(g)(ω)=⋁{μg(α)∣h(α)=ω,α∈Σ1*}, νh(g)(ω)=⋀{νg(α)∣h(α)=ω,α∈Σ1*} for any ω∈Σ2*.Proof.
(1) LetA,B∈ StepC(Σ). By Definition 17, we can assume A=(μA,νA)=∐i=1k(ai,bi)·1ℒi,B=(μB,νB)=∐j=1n(cj,dj)·1ℳj, where all ℒi and ℳj are classical context-free languages, 0≤ai+bi≤1,0≤cj+dj≤1,ai,bi,cj,dj∈[0,1],i∈Nk, and j∈Nn. With respect to the union, we have A∪B∈ StepC(Σ). That is, A∪B=(μA∪B,νA∪B)=(μA∨μB,νA∧νB), μA∪B(ω)=μA(ω)∨μB(ω)=(⋁i=1kai∧μ1ℒi(ω))∨(⋁j=1ncj∧μ1ℳj(ω)), νA∪B(ω)=νA(ω)∧νB(ω)=(⋀i=1kbi∨ν1ℒi(ω))∧(⋀j=1ndj∨ν1ℳj(ω)), for all ω∈Σ*.
With respect to the scalar product, for each(λ,θ)∈[0,1]×[0,1],0≤λ+θ≤1, we have (λ,θ)A=(λ∧μA,θ∨νA), (λ∧μA)(ω)=λ∧μA(ω)=λ∧(⋁i=1kai∧μ1ℒi(ω))=⋁i=1k((λ∧ai)∧μ1ℒi(ω)), (θ∨νA)(ω)=θ∨νA(ω)=θ∨(⋀i=1kbi∨ν1ℒi(ω))=⋀i=1k(θ∨bi)∨ν1ℒi(ω),forallω∈Σ*. By Definition 17, (λ,θ)A∈ StepC(Σ). For the reversal operation, ℒi-1={ω-1∈Σ*∣ω∈ℒi}, and ℒi-1 is a context-free language because ℒi is a context-free language, i∈Nk. For any ω∈Σ*,μA-1(ω)=μA(ω-1)=⋁i=1kai∧μ1ℒi(ω-1)=⋁i=1kai∧μ1ℒi-1(ω),νA-1(ω)=νA(ω-1)=⋀i=1kbi∨ν1ℒi(ω-1)=⋀i=1kbi∨ν1ℒi-1(ω), that is A-1∈ StepC(Σ). For the operation of concatenation, since μAB(ω)=⋁i=1k⋁j=1n(ai∧cj)∧μ1ℒiℳj(ω),νAB(ω)=⋀i=1k⋀j=1n(bi∨dj)∨ν1ℒiℳj(ω), for all ω∈Σ*, where the elements of the family set {ℒiℳj∣i∈Nk,j∈Nn} are also context-free languages since ℒi and ℳj are context-free languages. Hence AB∈ StepC(Σ).
For the Kleene closure,A*=(μA*,νA*) is defined by μA*(ω)=⋁{μA(ω1)∧⋯∧μA(ωk):k≥1,ω=ω1⋯ωk}, νA*(ω)=⋀{νA(ω1)∨⋯∨νA(ωk):k≥1,ω=ω1⋯ωk} for any ω∈Σ*. Since A∈ StepC(Σ), we assume that the IFSPDA ℳ=(Q,Σ,Γ,δ,q0,Z0,F) accepts A by Theorem 19. Let R={(μF(q),νF(q))∣q∈Q}∖{(0,1)}={(ai,bi)∣i∈Nk}. Then A=∐i=1k(ai,bi)·1ℒi, where ℒi is accepted by a PDA ℳi=(Q,Σ,Γ,δ′,q0,Z0,Fi), the mapping δ′:Q×(Σ∪{ε})×Γ→2Q×Γ* is defined by δ′(q,τ,X)={(p,γ)∣μδ(q,τ,X,p,γ)=1,p∈Q,γ∈Γ*}, for all (q,τ,X)∈Q×(Σ∪{ε})×Γ, and Fi={q∈Q∣μF(q)=ai,νF(q)=bi}, for all i∈Nk.
For any nonempty subsetJ of the set {1,2,…,k}, we can assume that J={i1,…,is}. Let rJ=ai1∧⋯∧ais,tJ=bi1∨⋯∨bis, and ℒ(J)=⋃p1⋯ps‍ℒp1+ℒp2+ℒp1*ℒp3+(ℒp1∪ℒp2)*⋯ℒps-1+(ℒp1∪⋯∪ℒps-2)*ℒps+(ℒp1∪⋯∪ℒps)*, where p1⋯ps is a permutation of {i1,…,is}, and ℒ(J) takes unions under all permutations of {i1,…,is}. Hence ℒ(J) is a context-free language. It is easily verified that A*=(∐∅≠J⊆Nk(rJ,tJ)·1ℒ(J))∪((μA(ε),νA(ε))·1{ε}). Therefore, A*∈ StepC(Σ).
(2) IfA∈ StepC(Σ2), then A=∐i=1k(ai,bi)·1ℒi, where ai,bi∈[0,1], ai+bi≤1, i∈Nk, and ℒ1,…,ℒk⊂Σ2* are classical context-free languages. Since h:Σ1*→Σ2* is a homomorphism, μh-1(A)(ω)=μA∘h(ω)=μA(h(ω))=⋁i=1kai∧μ1ℒi(h(ω))=⋁i=1kai∧μ1h-1(ℒi)(ω), and νh-1(A)(ω)=νA∘h(ω)=νA(h(ω))=⋀i=1kbi∨μ1ℒi(h(ω))=⋀i=1kbi∨ν1h-1(ℒi)(ω), where ω∈Σ1*,h-1(ℒi)={ω1∈Σ1*∣h(ω1)∈ℒi},i∈Nk, and the elements of the set {h-1(ℒi)∣i∈Nk} are classical context-free languages. Hence h-1(A)=A∘h=∐i=1k(ai,bi)·1h-1(ℒi). And so h-1(A)∈ StepC(Σ1). (3) If h(τ)≠ε, for all τ∈Σ, and g=(μg,νg)∈ StepC(Σ1), then μg(ω)=⋁i=1kai∧μ1ℒi(ω),νg(ω)=⋀i=1kbi∨μ1ℒi(ω), for any ω∈Σ1, where ai,bi∈[0,1], ai+bi≤1, i∈Nk, ℒ1,…,ℒk⊂Σ1* are classical context-free languages. Since h:Σ1*→Σ2* is a homomorphism, h(ℒi)={h(ω)∈Σ2*∣ω∈ℒi} is also a classical context-free language, i∈Nk. For any x∈Σ2*, μh(g)(x)=⋁{μg(α)∣h(α)=x}=⋁{⋁i=1kai∧μ1ℒi(α)∣h(α)=x}=⋁i=1kai∧μ1h(ℒi)(x), νh(g)(x)=⋀{νg(α)∣h(α)=x}=⋀{⋀i=1kbi∨ν1ℒi(α)∣h(α)=x}=⋀i=1kbi∨ν1h(ℒi)(x). Hence h(g)=(μh(g),νh(g))∈ StepC(Σ2).


## 5. Pumping Lemma for IFCFLs

In this section, we mainly discuss the pumping lemma for IFCFLs, which will become a powerful tool for proving a certain intuitionistic fuzzy language noncontext-free.Theorem 33.
LetA=(μA,νA) be an IFCFL over Σ*. Then there exists a finite natural number n such that for any z∈Σ* with n≤|z|, there have u,v,w,x,y,u1,v1,w1,x1,y1∈Σ* such that z=uvwxy=u1v1w1x1y1, |vwx|≤n, |v1w1x1|≤n, |vx|≥1, |v1x1|≥1, and μA(uviwxiy)≥μA(uvwxy),νA(u1v1iw1x1iy1)≤νA(u1v1w1x1y1), for all  i≥0.Proof.
LetA=(μA,νA) be an IFCFL over Σ*. Then there is an IFCNF G=(N,T,P,S) who accepts A. According to Proposition 29, ℒ(G)=∐‍(a,b)·1ℒ(Gab), where (a,b)∈(X∧∖{0})×(Y∨∖{1}), X=Im(μρ), Y=Im(νρ), 0≤a+b≤1 and the classical context-free grammar Gab=(N′,T,Pab′,S′) is shown in the proof process of of Proposition 29. Let G have m variables. That means, |N|=m. Choose n=2m. Next, suppose |z|≥n, μG(z)=a0>0 and νG(z)=b0<1. Then there exist bk∈Y∨∖{1} and al∈X∧∖{0} with 0<a0+bk≤1 and 0<al+b0≤1 such that z∈ℒ(Ga0bk)∩ℒ(Galb0). By pumping lemma for context-free languages, there are u,v,w,x,y∈Σ* satisfying z=uvwxy, |vwx|≤n and |vx|≥1 such that uviwxiy∈ℒ(Ga0bk), for all i≥0. Then μA(uviwxiy)≥μA(uvwxy) for any i≥0 since μA(uviwxiy)=⋁a∈X∧∖{0}a∧1ℒ(Gab)(uviwxiy)≥a0.
Similarly, there areu1,v1,w1,x1,y1∈Σ* satisfying z=u1v1w1x1y1, |v1w1x1|≤n and |v1x1|≥1 such that u1v1iw1x1iy1∈ℒ(Galb0), for all i≥0. Then νA(u1v1iw1x1iy1)≤νA(u1v1w1x1y1) for any i≥0 since νA(u1v1iw1x1iy1)=⋀b∈Y∨∖{1}b∨1ℒ(Gab)(u1v1iw1x1iy1)≤b0.Next, let us look at an example to negate an intuitionistic fuzzy language to be an IFCFL.Example 34.
LetA=(μA,νA) be an IFS over T*. The mappings μA,νA:T*→[0,1] are defined by
(27)μA(z)={0.5,ifz=aibjck(i<j<k),0,otherwise,νA(z)={0.3,ifz=aibjck(i<j<k),1,otherwise,
where i,j, and k are natural numbers.SupposeA is an IFCFL. Then there exists a certain IFCNF G such that ℒ(G)=A. For constant n, put z=anbn+1cn+2. Hence, μA(z)=μℒ(G)(z)=0.5 and νA(z)=νℒ(G)(z)=0.3. Let z=uvwxy, where |vwx|≤n and |vx|≥1. If vwx does not have c’s, then uv3wx3y has at least n+2a’s or b’s; if vwx has at least a c, then it has not an a since |vwx|≤n. And so uwy has na′s, but no more than 2n+2b’s and c’s in total, that is, |uwy|≤n+2n+2. Therefore, it is impossible that uwy has more b’s than a’s and also has more c’s than b’s. By calculation, we have μA(uwy)=0 and νA(uwy)=1. No matter how z is broken into uvwxy, we have a contradiction with Theorem 33. Therefore, A is not an IFCFL.The following example will show that intuitionistic fuzzy pushdown automata have more power than fuzzy pushdown automata when comparing two distinct strings although the degrees of membership of these strings recognized by the underlying fuzzy pushdown automata are equal.Example 35.
LetΣ={0,1}. Then L={ω1ω-1∣ω∈Σ*}⊆Σ* is clearly a context-free language but not a regular language by classical automata theory, where ω-1 represents the reversal of the string ω. Given an IFPDA ℳ=(Q,Σ,Γ,δ,I,Z0,F) and a fuzzy pushdown automaton 𝒩=(Q,Σ,Γ,η,σ0,Z0,σ1). Put Q={q0,q1,q2}, Γ={Z0,0,1}, an IFS δ=(μδ,νδ) in Q×(Σ∪{ε})×Γ×Q×Γ* is defined byμδ(q0,0,Z0,q0,0Z0)=0.7, νδ(q0,0,Z0,q0,0Z0)=0.2,μδ(q0,1,Z0,q0,1Z0)=0.6, νδ(q0,1,Z0,q0,1Z0)=0.3,μδ(q0,0,0,q0,00)=0.3, νδ(q0,0,0,q0,00)=0.6,μδ(q0,0,1,q0,01)=0.3, νδ(q0,0,1,q0,01)=0.5,μδ(q0,1,0,q0,10)=0.5, νδ(q0,1,0,q0,10)=0.4,μδ(q1,0,0,q1,ε)=0.6, νδ(q1,0,0,q1,ε)=0.3,μδ(q1,1,1,q1,ε)=0.5, νδ(q1,1,1,q1,ε)=0.35,μδ(q0,1,Z0,q1,Z0)=1, νδ(q0,1,Z0,q1,Z0)=0,μδ(q0,1,0,q1,0)=1, νδ(q0,1,0,q1,0)=0,μδ(q0,1,1,q1,1)=1, νδ(q0,1,1,q1,1)=0,μδ(q1,ε,Z0,q2,Z0)=1, νδ(q1,ε,Z0,q2,Z0)=0.
Otherwiseμδ(q,τ,Z,p,γ)=0 and νδ(q,τ,Z,p,γ)=1 for (q,τ,Z,p,γ)∈Q×(Σ∪{ε})×Γ×Q×Γ*.
The IFSsI=(μI,νI) and F=(μF,νF) in Q are defined by μI(q0)=1, νI(q0)=0, μI(q1)=μI(q2)=0, νI(q1)=μI(q2)=1, μF(q2)=1, νF(q2)=0, μF(q0)=μF(q1)=0 and νF(q0)=μF(q1)=1.
And setη=μδ, σ0=μI, and σ1=μF.
By computing with the strings, 010, 111, 01110, 10101, 0011100, and 1011101∈Σ*, we haveμℒ(ℳ)(010)=f𝒩(010)=0.6, νℒ(ℳ)(010)=0.3,μℒ(ℳ)(111)=f𝒩(111)=0.5, νℒ(ℳ)(111)=0.35,μℒ(ℳ)(01110)=f𝒩(01110)=0.5, νℒ(ℳ)(01110)=0.4,μℒ(ℳ)(10101)=f𝒩(10101)=0.3, νℒ(ℳ)(10101)=0.5,μℒ(ℳ)(0011100)=f𝒩(0011100)=0.3, νℒ(ℳ)(0011100)=0.6,μℒ(ℳ)(1011101)=f𝒩(1011101)=0.3, νℒ(ℳ)(1011101)=0.5.
This implies that 111 is better than 01110 because the degree of nonmembership ofνℒ(ℳ)(111) is smaller than the νℒ(ℳ)(01110)'s although the degrees of membership of the fuzzy context-free languages f𝒩(01110) and f𝒩(111) are equal. Comparing the above five strings, 010 is the best and 0011100 is the worst.


## 6. Conclusions

Taking intuitionistic fuzzy sets as the structures of truth values, we have investigated intuitionistic fuzzy context-free languages and established pumping lemma for the underlying languages. Firstly, the notions of intuitionistic fuzzy pushdown automata (IFPDAs) and their recognizable languages are introduced and discussed in detail. Using the generalized subset construction method, we show that IFPDAs are equivalent to IFSPDAs and then prove that intuitionistic fuzzy step functions are the same as those accepted by IFPDAs. Furthermore, we have presented algebraic characterization of intuitionistic fuzzy recognizable languages including decomposition form and representation theorem. It follows that the languages accepted by IFPDAs are equivalent to those accepted by IFPDAs∅ by classical automata theory. Secondly, we have introduced the notions of IFCFGs, IFCNFs, and IFGNFs. It is shown that they are equivalent in the sense that they generate the same classes of intuitionistic fuzzy context-free languages (IFCFLs). In particular, IFCFGs are proven to be an equivalence of IFPDAs as well. Then some operations on the family of IFCFLs are discussed. Finally pumping lemma for IFCFLs has been established. Thus, together with [38–40], we have more systematically established intuitionistic fuzzy automata theory as a generalization of fuzzy automata theory.As mentioned in Section1, IFS and fuzzy automata theory have supported a wealth of important applications in many fields. The next step is to consider the potential application of IFPDAs and IFCFLs such as in model checking and clinical monitoring. Additionally, many related researches in theories, such as IFPDAs based on the composition of t-norm and t-conorm and the minimal algorithm of IFPDAs, will be studied in the future.



---

*Source: 825249-2013-04-03.xml*