1 Introduction

It is well-known that the simplest and most important type of automata is finite-automata and it is closely related to formal language as finite-automata can be classified by the class of formal languages (cf., [5, 6, 25]). In finite automaton, the input alphabet consists of a finite number of discrete input symbols. Fuzzy automata proposed by Wee [30] considered as a generalization of finite automaton in which the knowledge about the system’s next state is vague or uncertain. Thereafter, a numerous works has been contributed towards the generalization of finite-automata by many authors such as Santos [23], Lee and Zadeh [10], Wechler [29], especially the most simplest one by Mordeson and Malik [13, 19]. Meanwhile, the notions of fuzzy languages generated by fuzzy grammars was firstly proposed by Lee and Zadeh [10]. In the last few decades, the relationship between fuzzy automata and its counterpart fuzzy grammars has been introduced and studied by may authors in many forms (cf., eg., [3, 4, 9, 11, 20,21,22, 24, 33, 34]). Among these studies, in [9], the concept of L-fuzzy grammar based on distributive lattice and Boolean lattice has been discussed; while [3] is towards the study of fuzzy grammars and recursively enumerable fuzzy languages. As a further extension, Moore et al. [20], Cheng and Wang [2] introduced quantum version of finite automata and grammars; while Qiu [21, 22] proposed automata theory based on the complete residuated lattice-valued logic. Meanwhile, Jan\(\check{c}\)i\(\acute{c}\) and \(\acute{C}\)iri\(\acute{c}\) [7] introduced Brzozowski type determinization for fuzzy automata, one of the canonization methods for computing fuzzy finite automata. Further, Mici\(\acute{c}\) et al. [17] figured one more determinization method for fuzzy finite automaton over a complete residuated lattice produces a minimal crisp-deterministic fuzzy automaton which is equivalent to the fuzzy finite automaton. In [24] and [4], Sheng and Guo studied about regular grammars with truth values in lattice-ordered monoid and discussed the relationship with languages. Subsequently, Li and Pedrycz [11] presented a basic framework of fuzzy finite automata with membership values in lattice-ordered monoids. Thereafter, Sheng and Li [24] introduced and studied the notions of lattice-valued finite automata and lattice-valued regular grammars. However, in [4], it has been found that the concept of lattice-valued grammars and lattice-valued regular grammars are not so satisfactory.

The notions of type-2 (T2) fuzzy sets was proposed by Zadeh [37], generalizing the existing type-1 (T1) fuzzy sets [36]. In [15], it has been pointed out that T1 fuzzy sets whose membership function is totally crisp provides limited platform for computational complexity and also not able to handle linguistic uncertainty involved in the model whereas T2 fuzzy set is capable to model such uncertainty because their membership functions are themselves fuzzy. Also, the membership function of T2 fuzzy sets is three dimensional which gives additional degrees of freedom to model the uncertainty directly in comparison to T1 fuzzy sets which have two-dimensional membership function. Unfortunately, T2 fuzzy sets are not easy to understand and use than are T1 fuzzy sets. In view of the difficulties involved in T2 fuzzy sets, Mendel and John [15] have tried to overcome the difficulties by giving a new representation of T2 fuzzy sets in a precise way and makes it easy to use and understand. Based on the idea of T2 fuzzy sets by Zadeh [37], Mizumoto and Tanaka [18] firstly proposed the notions of fuzzy-fuzzy automata (or T2 fuzzy automata). They investigated that T2 fuzzy languages characterized by T2 fuzzy automata is closed under the operations of union, intersection, concatenation and Kleene closure but are not closed under complement. The author in [35] has pointed out that all previous kind of fuzzy automata are still computing with values although a certain vagueness or uncertainty are involved in the process of computing. Afterward, Ying [35] proposed new kind of fuzzy automata considered as formal models of computing with words whose input is a string of T1 fuzzy subsets of the input alphabet, instead of a string of symbols from the input alphabet. However, researchers in [14, 28, 31] have been noticed the limitations of using T1 fuzzy sets in computing with words. Inspired by the work of Ying [35] on computing with words, recently, Jiang and Tang [8], introduced new kinds of formal model of computing with words into IT2 fuzzy environment named IT2 fuzzy automata and IT2 fuzzy pushdown automata whose inputs are strings of IT2 fuzzy subsets of the input alphabet. They have also studied the behavior of these automata and establish their relationship with IT2 fuzzy languages.

As we know, the characterization of fuzzy languages by fuzzy grammar is an important issue in computation theory. The present paper introduce and study the concept of grammar theory in the sense of IT2 fuzzy sets. That is, we propose IT2 fuzzy grammar and established their relationship with IT2 fuzzy automata. In particular, we get the following results (i) IT2 fuzzy weak regular grammar and IT2 fuzzy regular grammar generate the same classes of IT2 fuzzy languages (ii) if an IT2 fuzzy language is generated by an IT2 fuzzy grammar, it can be accepted by an IT2 fuzzy automata, and vice versa. Furthermore, we define some operations on IT2 fuzzy languages and show that IT2 fuzzy languages characterized by IT2 fuzzy automata is closed under the operations of union, intersection, concatenation and Kleene closure, but are not closed under complement.

2 Preliminaries

In this section, we recall some concepts related to type-2 fuzzy sets, IT2 fuzzy sets, IT2 fuzzy relation, and collect some results, which we need in the subsequent sections. Throughout this paper, X is a nonempty set, \(I=[0,1]\) and \([I]=\{[a,b]: a\le b, a,b\in I\}\).

We begin with the following:

Definition 2.1

[15] A T2 fuzzy set \(\tilde{A}\) is characterized by a type-2 membership function \(\mu _{\tilde{A}}: X\times J_x\rightarrow I\), \(\forall x\in X\) and \(J_{x}\subseteq I\), i.e.,

\(\tilde{A}=\{((x,u),\mu _{\tilde{A}}(x,u)): x\in X, u\in J_x\subseteq I\}\),

in which \(0\le \mu _{\tilde{A}}(x,u)\le 1\). \(\tilde{A}\) can also be expressed as

$$\begin{aligned} \tilde{A}=\int _{x\in X}\int _{u\in J_{x}} \mu _{\tilde{A}}(x,u)/(x,u), J_x\subseteq I, \end{aligned}$$

where \(\int \int \) denotes the union over all admissible x and u. For discrete universes of discourse \(\int \) is replaced by \(\sum \) .

Definition 2.2

[12, 16] A T2 fuzzy set \(\tilde{A}\) is called an IT2 fuzzy set if \(\mu _{\tilde{A}}(x,u)=1\), \(\forall x\in X\) and \(\forall u\in J_x\subseteq I\).

An IT2 fuzzy set \(\tilde{A}\) can be expressed as follows:

\(\tilde{A}=\{((x,u),1):x\in X, u\in J_x\}\)

or as:

$$\begin{aligned} \tilde{A}= & {} \int _{x\in X}\int _{u\in J_{x}} 1/(x,u), J_x\subseteq I. \end{aligned}$$

Definition 2.3

[15] Let \(\tilde{A}\) be a T2 fuzzy set in X. Then for each \(x'\in X\), a vertical slice \(\mu _{\tilde{A}}(x')\) of \(\tilde{A}\) is the intersection between the two-dimensional plane whose axes are \(u\in J_x\) and \(\mu _{\tilde{A}}(x',u)\) and the three dimensional type-2 membership function \(\tilde{A}\), i.e.,

$$\begin{aligned} \mu _{\tilde{A}}(x')\equiv \mu _{\tilde{A}}(x=x',u)=\int _{u\in J_{x'}} f_{x'}(u)/u, J_{x'}\subseteq I, \end{aligned}$$

in which \(0\le f_{x'}(u)\le 1\). Clearly, for an IT2F set \(\tilde{A}\), \(\mu _{\tilde{A}}(x=x',u)\) is defined as follows:

$$\begin{aligned} \mu _{\tilde{A}}(x')\equiv \mu _{\tilde{A}}(x=x',u)=\int _{u\in J_{x'}} 1/u, J_{x'}\subseteq I, \end{aligned}$$

By the abuse of notation, we shall write \(\mu _{\tilde{A}}(x)\) instead of \(\mu _{\tilde{A}}(x')\), \(\forall x'\in X\). It is a T1 fuzzy set, known as secondary membership function. The domain of a secondary membership function is called the primary membership of x, which we also called as secondary set.

In terms of vertical slice, an IT2 fuzzy set \(\tilde{A}\) can also be re-expressed as:

\(\tilde{A}=\{(x,\mu _{\tilde{A}}(x)):x\in X\}\)

or, as the following:

$$\begin{aligned} \tilde{A}=\int _{x\in X} \mu _{\tilde{A}}(x)/x=\int _{x\in X}\left[ \int _{u\in J_{x}} 1/u\right] /x, ~~where~ J_x\subseteq I \end{aligned}$$

is the primary membership of x.

In this paper, IT2F(X) will denote the set of all IT2 fuzzy sets in X.

If both X and \(J_x\) are discrete, \(\tilde{A}\in IT2F(X)\) can be expressed as follows

$$\begin{aligned} \tilde{A}= & {} \sum _{x\in X}\left[ \sum _{u\in J_x}1/u\right] /x=\sum _{i=1}^{N}\left[ \sum _{u\in J_{x_i}}1/u\right] /x_i\\= & {} \left[ \sum _{k=1}^{M_1}1/u_{1k}\right] /x_1+...+\left[ \sum _{k=1}^{M_i}1/u_{ik}\right] /x_i+...+\left[ \sum _{k=1}^{M_N}1/u_{Nk}\right] /x_N, \end{aligned}$$

where \(+\) denotes the union.

Throughout this paper, we consider both X and \(J_x\) are discrete.

In [15], it has been observed that x is discretized into N values and at each of these values u has been discretized into \(M_i\) values. The discretization along each \(u_{ik}\) does not have to be the same, however, if the discretization of each \(u_{ik}\) is the same, then \(M_1=M_2=...=M_N=M\).

Definition 2.4

[32, 38] The footprint of uncertainty, denoted by \(D\tilde{A}\), of a T2 fuzzy set \(\tilde{A}\) is given by

$$\begin{aligned} D\tilde{A}=\bigcup _{x\in X} J_{x}. \end{aligned}$$

Let \(D\tilde{A}(x)=J_{x}, \forall x\in X\). Then a T2 fuzzy set \(\tilde{A}\) can be re-expressed as:

$$\begin{aligned} \tilde{A}=\int \int _{(x,u)\in D\tilde{A}} \mu _{\tilde{A}}(x,u)/(x,u). \end{aligned}$$

For given T2 fuzzy set \(\tilde{A}\), a lower and an upper membership function are the two type-1 membership functions that are the bounds of \(D\tilde{A}\). The lower membership function (denoted as \(\underline{D}\tilde{A}\)) is associated with the lower bound of \(D\tilde{A}\), and the upper membership function (denoted as \(\overline{D}\tilde{A}\)) is associated with the upper bound of \(D\tilde{A}\).

For \(\tilde{A}\in IT2F(X)\) and \(x\in X\), \(\mu _{\tilde{A}}(x)\) is an IT1 fuzzy set on I. Thus \(D{\tilde{A}}(x)=\left[ \underline{D}\tilde{A}(x),\overline{D}\tilde{A}(x)\right] \), where \(\underline{D}\tilde{A}(x)\) and \(\overline{D}\tilde{A}(x)\) are lower and upper membership functions (both of which are T1 fuzzy sets) respectively. For simplicity, let \(D\tilde{A}(x)=\left[ l_{\tilde{A}}(x),r_{\tilde{A}}(x)\right] \). Consequently, the membership grade of each element of an IT2 fuzzy set is an interval \(\left[ l_{\tilde{A}}(x),r_{\tilde{A}}(x)\right] \).

Note that, any \(\tilde{A}\in IT2F(X)\) can also be represented as

$$\begin{aligned} \tilde{A}=1/D\tilde{A}. \end{aligned}$$

Now, we recall the following operations on IT2 fuzzy sets from [38].

Definition 2.5

Let \(\tilde{A}, \tilde{B}\in IT2F(X)\). Then \(\forall x\in X\),

  1. 1.

    the union of two IT2 fuzzy sets \(\tilde{A}, \tilde{B}\) is

    $$\begin{aligned} \tilde{A}\cup \tilde{B}=1/\left[ l_{\tilde{A}}(x)\vee l_{\tilde{B}}(x), r_{\tilde{A}}(x)\vee r_{\tilde{B}}(x)\right] \end{aligned}$$
  2. 2.

    the intersection of two IT2 fuzzy sets \(\tilde{A}, \tilde{B}\) is

    $$\begin{aligned} \tilde{A}\cap \tilde{B}=1/\left[ l_{\tilde{A}}(x)\wedge l_{\tilde{B}}(x), r_{\tilde{A}}(x)\wedge r_{\tilde{B}}(x)\right] \end{aligned}$$
  3. 3.

    the complement of IT2 fuzzy set \(\tilde{A}\) is

    $$\begin{aligned} \tilde{A}^c=1/\left[ 1-l_{\tilde{A}}(x), 1-r_{\tilde{A}}(x)\right] \end{aligned}$$
  4. 4.

    the scale product of \(\lambda \) and IT2 fuzzy set \(\tilde{A}\) is

    $$\begin{aligned} \lambda \cdot \tilde{A}=1/\left[ \underline{\lambda }\wedge l_{\tilde{A}}(x), \overline{\lambda }\wedge r_{\tilde{A}}(x)\right] , \end{aligned}$$

    where \(\lambda =1/\left[ \underline{\lambda }, \overline{\lambda }\right] \), \(\left[ \underline{\lambda }, \overline{\lambda }\right] \in Int([0,1])\), stands for the set of all closed subintervals of [0, 1].

  5. 5.

    the height of IT2 fuzzy set \(\tilde{A}\) is

    $$\begin{aligned} height(\tilde{A})=1/\left[ \vee _{x\in X} l_{\tilde{A}}(x), \vee _{x\in X} r_{\tilde{A}}(x)\right] \end{aligned}$$

We close this section by recalling the concept of fuzzy finite automaton from [35].

Definition 2.6

A fuzzy finite automaton (FFA) is a 5-tuple \(M=(Q,\Sigma ,\delta ,q_0,F)\), where

  1. (i)

    Q and \(\Sigma \) are nonempty finite sets called the state-set and input-set, respectively;

  2. (ii)

    \(q_{0}\in Q\) is called the initial state;

  3. (iii)

    F is a fuzzy subset of Q, called the fuzzy set of final states and for each \(q\in Q\), F(q) indicates intuitively the degree to which q is a final sate, and

  4. (iv)

    \(\delta : Q\times \Sigma \rightarrow F(Q)\), the set of all fuzzy subsets of Q, is a map called transition map. For any \(q\in Q\) and \(a\in \Sigma \), \(\delta (q,a)\) is a fuzzy subset of Q, and it may be seen as the possibility distribution of the states that the automaton in state q and with input a can enter. More explicitly, for each \(p\in Q\), \(\delta (q,a)(p)\) is the possibility degree to which the automaton in state q and with input a may enter state p.

To define the notion of the degree to which a string of input symbols is accepted by a fuzzy finite automaton, we need to extend the transition function. Let \(X^* = \bigcup _{n=0}^{\infty } X^n\) be the set of all strings of finite length over X and let \(\Lambda \) denote the empty string..

Definition 2.7

[35] Let \(M= (Q,X, \delta , q_0, F)\) be a FFA.

  1. 1.

    The transition function \(\delta \) is extended to \(\delta ^{*}: Q \times X^* \rightarrow F(Q),\) where

    $$\begin{aligned}&\delta (q, \Lambda ) = \frac{1}{q}\\&\delta ^{*}(q, wa) = \bigcup _{p\in Q} [\delta ^*(q,w)(p).\delta (p,a)] \end{aligned}$$

    for all \(w \in X^*\) and \(a \in X\), where \(\frac{1}{q}\) is a singleton in Q. i.e., the fuzzy subset of Q with membership 1 at q and with zero membership for all the other elements of Q. In addition, \(\delta (q,w)(p).\delta (p,a)\) stands for the scale product of fuzzy set \(\delta (p,a)\) with the parameter \(\delta (q,w)(p)\).

  2. 2.

    For any \(w \in X^*\), the degree to which w is accepted by M is

    $$\begin{aligned} L(M, w) = height (\delta ^*(q_0, w) \cap F). \end{aligned}$$
  3. 3.

    The language L(M) accepted by M is a fuzzy subset of \(X^*\) and it is defined by

    $$\begin{aligned} L(M)(w) = L (M,w), ~~\forall ~w \in X^*. \end{aligned}$$

2.1 IT2 fuzzy automata and its languages

In this section, we recall the concept of IT2 fuzzy finite automata and its languages from [8].

Definition 2.8

An interval type-2 fuzzy automaton (IT2 FA) is a five-tuple \(M= (Q, X, \delta , q_0, F)\), where

  1. 1.

    Q is a finite set of states;

  2. 2.

    X is a finite input alphabet;

  3. 3.

    \( q_0 \in Q\) is an initial state;

  4. 4.

    \(\delta \) is a mapping from \(Q \times X \) into IT2F(Q), the set of all IT2 fuzzy subsets of Q. For any \(q_i \in Q\) and \(a \in X\), \(\delta (q_i,a)\) is an IT2 fuzzy subset of Q, and it may be seen as the possibility distribution of the states that the automaton is state \(q_i\) and with input a can enter. More explicitly, for each \(q_j \in Q\), \(\delta (q_i, a)(q_j)\) is the possibility degree (i.e., T2 fuzzy membership degree) to which the automaton in state \(q_i\) and with input a may enter state \(q_j\). Formally, \(\delta (q_i,a)\) and \(\delta (q_i, a)(q_j)\)are defined as follows:

    $$\begin{aligned} \delta (q_i,a)= \frac{\left[ \sum _{k=1}^{M_0} \frac{1}{u_{0k}}\right] }{q_0}+...+\frac{\left[ \sum _{k=1}^{M_i}\frac{1}{u_{ik}}\right] }{q_i}+...+\frac{\left[ \sum _{k=1}^{M_N}\frac{1}{u_{Nk}}\right] }{q_N}, \end{aligned}$$

    where, \( u_{ik} \in J_x \subseteq [0,1], ~~ 0 \le i \le N.\)

    $$\begin{aligned} \delta (q_i,a)(q_j)= \frac{1}{\{u_{j1}, u_{j2}, \ldots , u_{jMj}\}}= \frac{1}{ [u_{j1}, u_{jMj}]},~where ~ \end{aligned}$$

    \(u_{jk} \in J_x \subseteq [0,1],\)    \(0 \le j \le N, ~~ 1 \le k \le M_j\).

  5. 5.

    F is an IT2 fuzzy subset of Q, called the IT2 fuzzy set of final states, and for each \(q_i \in Q\), \(F(q_i)\) indicates intuitively the degree to which \(q_i\) is a final state. That is, F and \(F(q_i)\) are define as follows:

    $$\begin{aligned} F= \frac{\left[ \sum _{k=1}^{M_0} \frac{1}{u_{1k}}\right] }{q_1}+...+\frac{\left[ \sum _{k=1}^{M_i}\frac{1}{u_{ik}}\right] }{q_i}+...+\frac{\left[ \sum _{k=1}^{M_N}\frac{1}{u_{Nk}}\right] }{q_N}, \end{aligned}$$

    where, \( u_{ik} \in J_x \subseteq [0,1], ~~ 1 \le i \le N.\)

    $$\begin{aligned} F(q_i)= \frac{1}{\{u_{i1}, u_{i2}, \ldots , u_{iMi}\}}= \frac{1}{ [u_{i1}, u_{iMi}]}, ~where, \end{aligned}$$

    \(u_{jk} \in J_x \subseteq [0,1],\)    \(1 \le i \le N, ~~ 1 \le k \le M_j\).

In view of Definitions 2.6 and 2.7, IT2 fuzzy finite automata can be considered as a generalizations of fuzzy finite automata as fuzzy finite automata are based on T1 fuzzy set; however, IT2 fuzzy finite automata are based on IT2 fuzzy sets.

Definition 2.9

[8] Let \(M= (Q,X, \delta , q_0, F)\) be an IT2 FA.

  1. 1.

    The transition function \(\delta \) is extended to \(\delta ^{*}: Q \times X^* \rightarrow IT2F(Q),\) where

    $$\begin{aligned} \delta (q, \Lambda )= & {} {1}/{[1,1]}/q\\ \delta ^{*}(q, wa)= & {} \bigcup _{p\in Q} [\delta ^{*}(q,w)(p).\delta (p,a)] \end{aligned}$$

    for all \(w \in X^*\) and \(a \in X\), where 1/[1, 1]/q (i.e., \({1}/{\{1\}}/q)\) is a singleton in Q. i.e., the IT2 fuzzy subset of Q with membership 1 (i.e., [1,1])at q and with zero membership (i.e., [0,0]) for all the other elements of Q. In addition, \(\delta (q,w)(p).\delta (p,a)\) stands for the scale product of IT2 fuzzy set \(~\delta (p,a)\) with the parameter \(\delta (q,w)(p).\)

  2. 2.

    For any \(w \in X^*\), the degree to which w is accepted by M is

    $$\begin{aligned} L(M, w) = height (\delta ^{*}(q_0, w) \cap F). \end{aligned}$$
  3. 3.

    An IT2 fuzzy language \(L(M)\in IT2F(X^*)\) accepted by M is defined as

    $$\begin{aligned} L(M)(w) = L (M, w), ~\forall ~w\in X^*, \end{aligned}$$

    where \(IT2F(X^*)\) denotes the set of all IT2 fuzzy sets in \(X^*\).

Example 2.1

Consider an IT2 FA \(M= (Q, X, \delta , q_0, F)\) where \(Q= \{q_0,q_1, q_2), X = \{a,b\} , F = {1}/{0.2}/q_1+ {1}/{0.3}/q_1 + {1}/{0.4}/q_1+{1}/{0.7}/q_2 +{1}/{0.9}/q_2 +{1}/{1}/q_2 \) \((or ~~F = {1}/{[0.2, 0.4]}/q_1 + {1}/{[0.7,1]}/q_2)\) and \(\delta \) is given by

$$\begin{aligned} \delta (q_0,a)= & {} {1}/{0.3}/q_1 + {1}/{0.5}/q_1 ,\\ \delta (q_1,a)= & {} {1}/{0.7}/q_1 + {1}/{0.8}/q_1 + {1}/{0.9}/q_1 + {1}/{0.3}/q_2 + {1}/{0.4}/q_2,\\ \delta (q_2,a)= & {} {1}/{0.5}/q_2 + {1}/{0.7}/q_2 ,\\ \delta (q_1,b)= & {} {1}/{0.3}/q_1 + {1}/{0.4}/q_1 + {1}/{0.4}/q_2 + {1}/{0.6}/q_2 ,\\ \delta (q_2,b)= & {} {1}/{0.2}/q_1 + {1}/{0.3}/q_1 + {1}/{0.5}/q_1 + {1}/{0.7}/q_2 + {1}/{0.8}/q_2. \end{aligned}$$

If \(w = aaab\), we have the following:

$$\begin{aligned} \delta (q_0,a)= & {} {1}/{0.3}/q_1 + {1}/{0.5}/q_1 = {1}/{[0.3,0.5]}/q_1,\\ \delta ^*(q_0,aa)= & {} {1}/{[0.3,0.5]}.\delta (q_1,a)\\= & {} {1}/{[0.3,0.5]}.({1}/{[0.7, 0.9]}/q_1 + {1}/{[0.3, 0.4]}/q_2 \\= & {} {1}/{[0.3, 0.5]}/q_1 + {1}/{[0.3, 0.4]}/q_2\\ \delta ^*(q_0,aaa)= & {} {1}/{[0.3, 0.5]}.\delta (q_1,a) \cup {1}/{[0.3, 0.4]}.\delta (q_2,a)\\= & {} {1}/{[0.3, 0.5]}.({1}/{[0.7, 0.9]}/q_1 + {1}/{[0.3, 0.4]}/q_2) \\&\cup ~ {1}/{[0.3, 0.4]}.({1}/{[0.5, 0.7]}/q_2)\\= & {} ({1}/{[0.7, 0.9]}/q_1 + {1}/{[0.3, 0.4]}/q_2) \cup ({1}/{[0.3, 0.4]}/q_2) \\= & {} {1}/{[0.3, 0.5]}/q_1 + {1}/{[0.3, 0.4]}/q_2\\ \delta ^*(q_0,aaab)= & {} {1}/{[0.3, 0.5]}.\delta ((q_1,b) \cup {1}/{[0.3, 0.4]}.\delta (q_2,b))\\= & {} {1}/{[0.3, 0.5]}.({1}/{[0.3, 0.4]}/q_1 + {1}/{[0.4, 0.6]}/q_2 ) \\&\cup ~ {1}/{[0.3, 0.4]}.({1}/{[0.2, 0.5]}/q_1 + {1}/{[0.7, 0.8]}/q_2 )\\= & {} ({1}/{[0.3, 0.4]}/q_1 + {1}/{[0.3, 0.5]}/q_2 )\\&\cup ~({1}/{[0.2, 0.4]}/q_1 + {1}/{[0.3, 0.4]}/q_2 )\\= & {} {1}/{[0.3, 0.4]}/q_1 + {1}/{[0.3, 0.5]}/q_2.\\ \delta ^*(q_0, aaab) \cap F= & {} ({1}/{[0.3, 0.4]}/q_1 + {1}/{[0.3, 0.5]}/q_2)\\&\cap ~({1}/{[0.2, 0.4]}/q_1 + {1}/{[0.7,1]}/q_2) \\= & {} {1}/{[0.2, 0.4]}/q_1 + {1}/{[0.3, 0.5]}/q_2. \end{aligned}$$

The degree to which string aaab of values accepted by M is

$$\begin{aligned} L(M, aaab)= & {} height (\delta ^*(q_0, aaab) \cap F)\\= & {} height ({{1}/{[0.3,0.4]}}/q_1 + {{1}/{[0.3,0.5]}}/q_2)\\= & {} {{1}/{[\vee \{0.3,0.3\}, \vee \{ 0.4, 0.5\}]}}\\= & {} {{1}/{[0.3, 0.5]}}. \end{aligned}$$

3 IT2 fuzzy grammar and IT2 fuzzy automata

In this section we introduce and study the concept of IT2 fuzzy grammar and establish their relationship with IT2 fuzzy languages.

Definition 3.1

An IT2 fuzzy grammar (IT2 FG) is a quadruple \(G= (N, T, P, S)\), where

  1. 1.

    N is a finite alphabet of nonterminal symbols,

  2. 2.

    T is a finite alphabet of terminal symbols, such that \(N \cap T = \phi \),

  3. 3.

    \(S \in N\) is a starting nonterminal symbol,

  4. 4.

    P is a finite collection of IT2 fuzzy productions over \(N \cup T\) such that \(P = \{\alpha \xrightarrow {\rho } \beta |\alpha \in (N \cup T)^{*} N(N \cup T)^{*}, ~\beta \in (N \cup T)^{*}\}\), where \(\rho \) is a mapping from \((N \cup T)^{*} \times (N \cup T)^{*}\) to \(IT2F(T^*)\), called IT2 fuzzy transition function.

We may interpret \(\rho (\alpha , \beta )\) as the grade of membership that \(\alpha \) will be replaced by \(\beta \), denoted by \(\rho (\alpha , \beta )=\rho (\alpha \rightarrow \beta )\). For the sake of convenience, \(\alpha {\overset{\rho }{\rightarrow }} \beta \) is sometimes written as \(\alpha \rightarrow \beta \) in P.

Definition 3.2

Let \(\alpha \xrightarrow {\rho } \beta \) be a production and \(\gamma , \delta \in (N \cup T)^*\). Then \(\gamma \beta \delta \) is said to be directly derivable from \(\gamma \alpha \delta \), which we shall denote by

\(\gamma \alpha \delta {\overset{\rho }{\Longrightarrow }} \gamma \beta \delta \).

If \(\alpha _i \in (N \cup T)^*\), for \(i = 1,2,3,...,m\) and \(\alpha _{i+1}\) is directly derivable from \(\alpha _i\) for \(i = 1,2,3,...,m-1\), then \(\alpha _i\) is said to derive \(\alpha _m\) in grammar G or \(\alpha _m\) is derivable from \(\alpha _1\) in grammar G, which we shall denoted by \(\alpha _1 \underset{G}{\overset{\rho }{\Longrightarrow }}^{*} \alpha _m\). We call

$$\begin{aligned} \alpha _1 {\overset{\rho _1}{\Longrightarrow }} \alpha _2 {\overset{\rho _2}{\Longrightarrow }} \alpha _3 {\overset{\rho _3}{\Longrightarrow }} ... {\overset{\rho _{m-1}}{\Longrightarrow }}\alpha _m. \end{aligned}$$

the derivation chain of \(\alpha _m\) from \(\alpha _1\), and define

$$\begin{aligned} \rho = height( \rho _1 \cap \rho _2 \cap \rho _3 \cap ...\cap \rho _{m-1}) \end{aligned}$$

Definition 3.3

Let \(G=(N, T,P, S)\) be an IT2 FG. An IT2 fuzzy language \(L(G)\in IT2F(T^*)\) generated by G is defined as

$$\begin{aligned} L(G, w) = height\{ \rho : S \underset{G}{\overset{\rho }{\Longrightarrow }}^{*} w~|~ w \in T^*\}, \end{aligned}$$

where \(IT2F(T^*)\) denotes the set of all IT2 fuzzy sets in \(T^*\).

Example 3.1

Let \(G\!=\! (N,T, P,S)\) be an IT2 FG, where \( N \!=\! (S, A, B), T = \{a\}\) and \( P = \Big \{ S\xrightarrow {{1/[0.1,0.2]}}aS,S\xrightarrow {{1/[0.3,0.7]}}aA,A\xrightarrow {{1/[0.5,0.7]}}aA,A\xrightarrow {{1/[0.3,0.4]}}aB, B\xrightarrow {{1/[0.7,0.9]}}aS \Big \}\).

If the derivations of \(w= (aaa)\) in G are as follows:

  1. 1.

    \( S \xrightarrow {{1}/{[0.1,0.2]}} a S \xrightarrow {{1}/{[0.1,0.2]}} a S \xrightarrow {{1}/{[0.1,0.2]}} a S\),

  2. 2.

    \( S \xrightarrow {{1}/{[0.1,0.2]}} a S \xrightarrow {{1}/{[0.1,0.2]}} a S \xrightarrow {{1}/{[0.3,0.7]}} a A\),

  3. 3.

    \( S \xrightarrow {{1}/{[0.1,0.2]}} a S \xrightarrow {{1}/{[0.3,0.7]}} a A \xrightarrow {{1}/{[0.5,0.7]}} a A\),

  4. 4.

    \( S \xrightarrow {{1}/{[0.3,0.7]}} a A \xrightarrow {{1}/{[0.5,0.7]}} a A \xrightarrow {{1}/{[0.5,0.7]}} a A\),

  5. 5.

    \( S \xrightarrow {{1}/{[0.3,0.7]}} a A \xrightarrow {{1}/{[0.3,0.4]}} a B \xrightarrow {{1}/{[0.7,0.9]}} a S\), then

$$\begin{aligned} L(G, w)= & {} height\{{{1}/{[0.1,0.2]}}\cap {{1}/{[0.1,0.2]}} \cap {{1}/{[0.1,0.2]}},\\&~~~~~~~~~{{1}/{[0.1,0.2]}} \cap {{1}/{[0.1,0.2]}},{{1}/{[0.3,0.7]}}, \\&~~~~~~~~~{{1}/{[0.1,0.2]}} \cap ~{{1}/{[0.3,0.7]}} \cap {{1}/{[0.5,0.7]}},\\&~~~~~~~~~{{1}/{[0.3,0.7]}} \cap {{1}/{[0.5,0.7]}} \cap {{1}/{[0.5,0.7]}},\\&~~~~~~~~~{{1}/{[0.3,0.7]}} \cap {{1}/{[0.3,0.4]}} \cap {{1}/{[0.7,0.9]}} \}\\= & {} height \{ {{1}/{[0.1,0.2]}},{{1}/{[0.1,0.2]}},{{1}/{[0.1,0.2]}},{{1}/{[0.3,0.7]}},\\&~~~~~~~~~{{1}/{[0.3,0.4]}}\}\\= & {} {{1}/{[\vee \{0.1,0.1, 0.1,0.3,0.3\}, \vee \{ 0.2, 0.2,0.2,0.7, 0.4\}]}}\\= & {} {{1}/{[0.3, 0.7]}}. \end{aligned}$$

Definition 3.4

(Chomsky-like classification) Let \(G = (N, T, P, S)\) be an IT2 FG. Then G is said to be

  1. 1.

    arbitrary if there are no restrictions on the form of IT2 fuzzy productions rules, i.e., productions are of the general form \(\alpha {\overset{\rho }{\Longrightarrow }} \beta \), \(\alpha , \beta \in (N\cup T)^*\). Accordingly, \(L_G\) is called IT2 fuzzy type 0 language;

  2. 2.

    monotone or context-sensitive if for every production \(\alpha \xrightarrow {\rho } \beta \in P\) , \(\alpha , \beta \in (N \cup T)^*\), implies \(|\alpha |\le |\beta |\). Accordingly, \(L_G\) is called IT2 fuzzy context-sensitive language;

  3. 3.

    context free if for every production \(\alpha \xrightarrow {\rho } \beta \in P,\) \(\alpha , \beta \in (N \cup T)^{*} \) implies \(\vert \alpha \vert \le \vert \beta \vert \) and \(\alpha \in N\). Accordingly, \(L_G\) is called IT2 fuzzy context free language;

  4. 4.

    week regular if for every production \(\alpha \xrightarrow {\rho } \beta \in P, \alpha , \beta \in (N \cup T)^*\) implies \(\alpha \in N\) and \(\beta \in T^{+} B\), \(B \in N \cup \{\Lambda \}\) or \(\alpha = S, \beta = \Lambda \). Accordingly, \(L_G\) is called IT2 fuzzy week regular language;

  5. 5.

    regular if for every production \(\alpha \xrightarrow {\rho } \beta \in P, \alpha , \beta \in (N \cup T)^*\), \(\rho (\alpha , \beta )>1/[0, 0]\) implies \(\alpha \in N\) and \(\beta \in TB\), \(B \in N \cup \{\Lambda \}\) or \(\alpha = S, \beta = \Lambda \). Accordingly, \(L_G\) is called IT2 fuzzy regular language.

Definition 3.5

Two IT2 FGs \(G_1\) and \(G_2\) are said to be equivalent if they generate the same IT2 fuzzy language, i.e., \(L(G_1) = L(G_2)\).

Theorem 3.1

An IT2 fuzzy weak regular grammar is equivalent to IT2 fuzzy regular grammar, i.e., they generate the same classes of IT2 fuzzy languages.

Proof

Let \(G_1= ({N_1}, {T}, P_1, S)\) and \(G= (N_, T, P, S)\) ba an IT2 week and IT2 regular grammar respectively. Also, let the languages generated by \(G_1\) and G are denoted by \(L(G_1)\) and L(G) respectively. We need to show that \(L(G_1)=L(G) \). In view of Definition 3.4, it is easy to see that \(L(G) \subseteq L(G_1)\). In the following, we only need to show that \(L(G_1)\subseteq L(G) \).

(i) For each production

\(\alpha \rightarrow w_1 w_2\cdots w_m \beta \in P_1\),

where \(w_i \in {T_1}\) for \( i=1, 2,\cdots , m\) and \(\alpha \beta \in {N_1}\). When \(m=1\), we have \(w_1 \in T, \alpha , \beta \in {N_1} \subseteq N\) and \( \alpha \rightarrow w_1 \beta \in P \) as required, while if \(m \ge 2, \alpha , \beta \in {N_1} \subseteq N\), we can define new nonterminal symbols as \(\lambda _1, \lambda _2, \cdots , \lambda _{m-1} \in N\) and denote the set of these symbols as \( {N_0}\), then we have \( N = {N_1}\cup {N_0}\).

Let \( \rho _G \) and \(\rho _{G_1}\) represent the grade of membership of productions in G and \(G_1\) respectively. Now we can reproduce the production \(\alpha \rightarrow w_1 w_2 \cdots w_m \beta \) by means of productions \(\alpha \rightarrow w_1 \lambda _1, \lambda \rightarrow w_2 \lambda _2, \cdots , \lambda _{m-1} \rightarrow w_m \beta \in P\) with \(\rho _G(\alpha \rightarrow w_1 \lambda _1) = \rho _G (\lambda _1 \rightarrow w_2 \lambda _2) = \cdots = \rho _G(\lambda _{m-2} \rightarrow w_{m-1} \lambda _{m-1}) = 1/[1,1];\) \( \rho _G(\lambda _{m-1} \rightarrow w_m \beta ) = \rho _{G_1} (\alpha \rightarrow w_1 w_2 \cdots w_m \beta ).\) Then

$$\begin{aligned} \rho _G (\alpha \rightarrow w_1 w_2 \cdots w_m \beta )= & {} \rho _G(\alpha \rightarrow w_1 \lambda _1) \cap \rho _G(\lambda _1 \rightarrow w_2 \lambda _2)\cap \cdots \cap \\&\rho _G( \lambda _{m-2} \rightarrow w_{m-1} \lambda _{m-1}) \cap \rho _G(\lambda _{m-1} \rightarrow w_m \beta )\\= & {} \rho _{G_1}(\alpha \rightarrow w_1 w_2 \cdots w_m \beta ). \end{aligned}$$

(ii) For each production

\(\alpha \rightarrow v_1 v_2\cdots v_m \in P_1\),

where \(v_i \in {T_1}\) for \( i=1, 2,\cdots , n\) and \(\alpha \in {N_1}\). When \(n=1\), we have \(v_1 \in T\) and \(\alpha \rightarrow v_1 \in {P}\) as required, while if \(n \ge 2, \alpha , \in {N_1} \subseteq N\), we define new nonterminal symbols as \(\mu _1, \mu _2, \cdots , \mu _{n-1} \in N\) and denote the set of these symbols as \( {N_0}\), then we have \( N = {N_1}\cup {N_0}\).

Now, we can reproduce the production \(\alpha \rightarrow v_1 v_2 \cdots v_n \beta \) by means of productions \(\alpha \rightarrow v_1 \mu _1, \mu _1 \rightarrow v_2 \mu _2, \cdots , \mu _{n-1} \rightarrow v_n \in P\) with \(\rho _G(\alpha \rightarrow v_1 \mu _1) = \rho _G (\mu _1 \rightarrow v_2 \mu _2) = \cdots =\rho _G(\mu _{n-2} \rightarrow v_{n-1} \mu _{n-1}) = 1/[1,1];\) \( \rho _G(\mu _{n-1} \rightarrow v_n ) = \rho _{G_1} (\alpha \rightarrow v_1 v_2 \cdots v_n ).\) Then

$$\begin{aligned} \rho _G (\alpha \rightarrow v_1 v_2 \cdots v_n )= & {} \rho _G(\alpha \rightarrow v_1 \mu _1) \cap \rho _G(\mu _1 \rightarrow v_2 \mu _2)\cap \cdots \cap \\&\rho _G( \mu _{n-2} \rightarrow v_{n-1} \mu _{n-1}) \cap \rho _G(\mu _{n-1} \rightarrow v_n )\\= & {} \rho _{G_1}(\alpha \rightarrow v_1 v_2 \cdots v_n ). \end{aligned}$$

Thus, G can be specified is an IT2 fuzzy regular grammar. Therefore, from \( \alpha \rightarrow w_1 w_2 \cdots w_m \beta \in P\) and \( \alpha \rightarrow v_1 v_2 \cdots v_n \in P\) we conclude that \(L(G_1) \subseteq L(G)\).

To prove the reverse inclusion, suppose that for some \(w \in T^{*}\), there is a deviation

\( {S}{\overset{\rho }{\Longrightarrow }}^{*} w\).

in \(G_2\) with \(\rho _{G_2}(S \rightarrow w) = \rho _G(S \rightarrow w).\)

We shall show that there is a derivation of w in \(G_1\) by induction on the number of symbols from \( N N_1 \) appearing in the derivation \({S}{\overset{\rho }{\Longrightarrow }}^{*} w\). If no such symbols appear then \({S}{\overset{\rho }{\Longrightarrow }}^{*} w\) is already a deviation in \(G_1\). Otherwise the first appearance of a symbol of \(N \ N_1\) is based either on a production \( \alpha \rightarrow w_1 \lambda _1\) with \(\rho _{G_2} (\alpha \rightarrow w_1 \lambda _1) = \rho _{G} (\alpha \rightarrow w_1 \lambda _1) \), where \(\alpha \rightarrow w_1 w_2 \cdots w_m \beta \) is a production in \(G_1\), or on a production \( \alpha \rightarrow v_1 \mu _1\) with \(\rho _{G_2} (\alpha \rightarrow v_1 \mu _1) = \rho _{G} (\alpha \rightarrow v_1 \mu _1) \), where \(\alpha \rightarrow v_1 v_2 \cdots v_n \) is a production in \(G_1\). Now consider the first case, for any of the symbols of \(N \ N_1\), the only way in which \(\mu _i\) can subsequently appear must involve changes from \(\lambda _1\) to \(w_2 \lambda _2, \cdots , \lambda _{m-1} \) to \( w_m \beta \). Then the chain of transitions \( \alpha \rightarrow w_1 \lambda _1, \lambda _1 \rightarrow w_2 \lambda _2, \cdots , \lambda _{m-1} \rightarrow w_m \beta \) with

$$\begin{aligned}&\rho _{G_2} (\alpha \rightarrow w_1 \lambda _1) = \rho _{G} (\alpha \rightarrow w_1 \lambda _1) \\&\rho _{G_2} (\lambda _1 \rightarrow w_2 \lambda _2) = \rho _{G} (\lambda _1 \rightarrow w_2 \lambda _2)\\&\cdots \cdots \cdots \cdots \\&\rho _{G_2} (\lambda _{m-1} \rightarrow w_m \beta ) = \rho _{G} (\lambda _{m-1} \rightarrow w_m \beta ) \end{aligned}$$

can be reproduced by a single transition \( \alpha \rightarrow w_1 w_2 \cdots w_m \beta \) in G with

$$\begin{aligned} \rho _{G_2} (\alpha \rightarrow w_1 w_2 \cdots w_m \beta )= & {} \rho _{G_2} (\alpha \rightarrow w_1 \lambda _1) \cap \rho _{G_2} (\lambda _1 \rightarrow w_2 \lambda _2) \cap \cdots \cap \\&\rho _{G_2} (\lambda _{m-1} \rightarrow w_m \beta ) \\= & {} \rho _{G} (\alpha \rightarrow w_1 \lambda _1) \cap \rho _{G} (\lambda _1 \rightarrow w_2 \lambda _2) \cap \cdots \cap \\&\rho _{G} (\lambda _{m-1} \rightarrow w_m \beta ) \\= & {} \rho _{G} (\alpha \rightarrow w_ {w_2} \cdots w_m \beta )\\= & {} \rho _{G_1} (\alpha \rightarrow w_ {w_2} \cdots w_m \beta ). \end{aligned}$$

Similarly, in the second case the derivation must involve subsequently changes from \(m_1\) to \(v_2 \mu _2, \cdots , \mu _{n-1} \) to \(v_n\), and these n transitions can be replaced by a single transitions in \(G_2\) from w to \(v_1 v_2 \cdots v_n \) with

$$\begin{aligned} \rho _{G_2} (\alpha \rightarrow v_1 v_2 \cdots v_n )= & {} \rho _{G_2} (\alpha \rightarrow v_1 \mu _1) \cap \rho _{G_2} (\mu _1 \rightarrow v_2 \mu _2) \cap \cdots \cap \\&\rho _{G_2} (\mu _{n-1} \rightarrow v_n ) \\= & {} \rho _{G} (\alpha \rightarrow v_1 \mu _1) \cap \rho _{G} (\mu _1 \rightarrow v_2 \mu _2) \cap \cdots \cap \\&\rho _{G} (\mu _{n-1} \rightarrow v_n ) \\= & {} \rho _{G} (\alpha \rightarrow v_1 v_2 \cdots v_n )\\= & {} \rho _{G_1} (\alpha \rightarrow v_{v_2} \cdots v_n \beta ). \end{aligned}$$

In both cases, the derivation \({S}{\overset{\rho }{\Longrightarrow }}^{*} w\) is replaced by one with fewer occurrence of symbols from \(N \ N_1\) with \( \rho _{G_2} (w) = \rho _{G}(w)\), then it follows that \(L(G_2) \subset L(G_1)\). Thus \(L(G) \subset L(G_1)\), showing that \(L(G) = L(G_1)\).

The following example illustrate above proposition.

Example 3.2

Let \(G_1 = (N_1, T, P_1, S)\) be an IT2 fuzzy week regular grammar, where \(N_1 = \{S, A, B\}\), and \(T =\{x, y, z\} \),

\(P_1= \{ {S}{\overset{\rho _1}{\longrightarrow }} x x A, ~~{A}{\overset{\rho _2}{\longrightarrow }} x y B, ~~{B}{\overset{\rho _3}{\longrightarrow }} y A, ~~{A}{\overset{\rho _4}{\longrightarrow }} z y, ~~{B}{\overset{\rho _5}{\longrightarrow }} z a \}.\)

We construct an IT2 fuzzy regular grammar \(G = (N, T, P, S)\), where

$$\begin{aligned} P= & {} \{ {S}{\overset{1/[1,1]}{\longrightarrow }} x \lambda _1, ~~~{\lambda _1}{\overset{\rho _1}{\longrightarrow }} x A, ~~~{A}{\overset{1/[1,1]}{\longrightarrow }} x \lambda _2,~~~{\lambda _2}{\overset{\rho _2}{\longrightarrow }} y B,\\&{B}{\overset{\rho _3}{\longrightarrow }} y A ,~~~{A}{\overset{1/[1,1]}{\longrightarrow }} z \mu _1 , ~~~{\mu _1}{\overset{\rho _4}{\longrightarrow }} y ,~~~{B}{\overset{1/[1,1]}{\longrightarrow }} z \mu _2 ,~~~{\mu _2}{\overset{\rho _5}{\longrightarrow }} x, \}. \end{aligned}$$

and \(N= N_1 \cup \{\lambda _1, \lambda _2, \mu _1, \mu _2\}\).

Clearly, for \(w = x^3 y^2 z y\) the derivation of w in \(G_1\) is as follows:

\({S}{\overset{\rho _1}{\longrightarrow }} x x {A} {\overset{\rho _2}{\longrightarrow }} x x x y {B}{\overset{\rho _3}{\longrightarrow }} x x x y y {A}{\overset{\rho _4}{\longrightarrow }} x x x y y z y\),

so \(L(G_1) (w) = \rho _1 \cap \rho _2 \cap _3 \cap \rho _4\).

The derivation of w in G is as follows:

$$\begin{aligned}&{S} {\overset{1/[1,1]}{\longrightarrow }} x {\lambda _1} ~~{\overset{\rho _1}{\longrightarrow }} x x {A}~~{\overset{1/[1,1]}{\longrightarrow }} x x x {\lambda _2}~~{\overset{\rho _2}{\longrightarrow }} x x x y {B}~~{\overset{\rho _3}{\longrightarrow }} x x x y y {A}\\&{\overset{1/[1,1]}{\longrightarrow }} x x x y y z {\mu _1}~~{\overset{\rho _4}{\longrightarrow }} x x x y y z y . \end{aligned}$$

then

$$\begin{aligned} L(G)(w)= & {} 1/[1,1] \cap \rho _1 \cap 1/[1,1] \cap \rho _2 \cap \rho _3 \cap 1/[1,1] \cap \rho _4 \\= & {} \rho _1 \cap \rho _2 \cap \rho _3 \cap \rho _4\\= & {} L(G_1)(w). \end{aligned}$$

Now we have following result.

Theorem 3.2

Let \(G=(N, T, P, S)\) be an IT2 fuzzy regular grammar, then there exists an IT2 FA \(M=(Q, X, \delta , q_0, F)\) such that \(L(M) = L(G)\).

Proof

For given an IT2 fuzzy regular grammar \(G=(N, T, P, S)\), we can construct an IT2 FA \(M=(Q, X, \delta , q_0, F)\), where \( Q = N \cup q_F,~ X = T, ~q_0 = {1}/{[1,1]}/ S ,~ F = ({1}/{[1,1]}/ S + L_G(\Lambda )/ q_F\)) and a/b

$$\begin{aligned} \delta (A, u) (B) =\left\{ \begin{array}{ll} \rho ( A \rightarrow u B) &{} A, B \in N\\ \rho (A \rightarrow u) &{} A \in N, B = F \\ 0 &{} \text{ otherwise } \end{array} \right. \end{aligned}$$

For any \(\lambda , \mu \in (N \cup T)^*, \rho ( \lambda \rightarrow \mu ) = height \{\rho : \lambda {\overset{\rho }{\Longrightarrow }}^{*} \mu \}.\) We will show that \(L(M)(w) = L(G)(w)\). Let \(w \in V_T^*\), there are two cases for w.

  1. 1.

    If \(w = \Lambda \), then \(L(M)(w) = L(G)(\Lambda )\).

  2. 2.

    If \(w \ne \Lambda \), let \(w = u_1u_2u_3...u_n,\) where \(u_i \in T\) for \(i = 1,2,...,n.\) If \(S {\overset{\rho }{\Longrightarrow }}^* w\) there must exist some derivation of w with the form

    $$\begin{aligned} S&{\overset{\rho _1}{\Longrightarrow }}&u_1~A_1\\&{\overset{\rho _2}{\Longrightarrow }}&u_1u_2~A_2\\&{\overset{\rho _3}{\Longrightarrow }}&\ldots \ldots \ldots \\&{\overset{\rho _{n-1}}{\Longrightarrow }}&u_1u_2 \ldots u_{n-1}~A_{n-1}\\&{\overset{\rho _n}{\Longrightarrow }}&u_1u_2 \ldots u_{n-1}u_n. \end{aligned}$$

where \(A_{i-1}{\overset{\rho _i}{\Longrightarrow }} u_iA_i \in P\) for \(i = 1, 2, ..., n\) and \(A_0 =S\), \(A_n = u_n\) with \( \rho = \rho _1 \cap \rho _2\cap \rho _3\cap ... \cap \rho _n.\)

By the definition of \(\delta ^*\) of IT2 FA, we get

$$\begin{aligned} \delta ^*(S,w)(F)\supseteq & {} \delta (S, u_1)(A_1)\wedge \delta (A_1, u_2)(A_2)\wedge ... \delta (A_{n-1}, u_n)(F)\\= & {} \rho _1 \cap \rho _2 \cap ....\cap \rho _n\\= & {} \rho . \end{aligned}$$

Hence, \(L(M)(w)= height( \delta ^*(S,w)\cap F)= \delta ^*(S, w)(F) \ge \rho .\)

Thus, we have shown that \(L(G)(w) \subseteq L(M)(w)\) for any \(w \in X^*\), that is \(L(G) \subseteq L(M)\).

Conversely, if \(L(M)(w) = \delta ^*( S,w)(F) \supseteq \delta (S, u_1)(A_1)\wedge \delta (A_1, u_2)(A_2)\wedge \ldots ~ \delta (A_{n-1}, u_n)(F) \) For any \(A_i \in Q,\) let

$$\begin{aligned}&\delta (S,u_1)(A_1)=\rho _1,\\&\delta (S,u_2)(A_2)=\rho _2,\\&\ldots \ldots \ldots \ldots \ldots \\&\delta (A_{n-1},u_n)(A_n)=\rho _n, \end{aligned}$$

and let

$$\begin{aligned} \rho = \rho _1 \cap \rho _2\cap \rho _3\cap ... \cap \rho _n, \end{aligned}$$

then there exists corresponding derivation \(S {\overset{\rho }{\Longrightarrow }}^* w\). Then it shows that if \(\rho \subseteq L(M)(w)\), then \(\rho \subseteq L(G)(w)\), that \(L(M) \subseteq L(G)\). Therefore, \(L(M) = L(G)\), that is, IT2 fuzzy languages can be accepted by IT2 fuzzy automata.

We give an example to illustrate the proof of the above theorem.

Example 3.3

Consider an IT2 fuzzy regular grammar \(G= (N, T, P, S)\) given in Example 3.2. An equivalent IT2 FA \(M =( Q, X, \delta , q_0, F)\) is constructed as follows: \(Q = N \cup q_F = \{ S, A, B, q_F\}, X = T =\{a\}, q_0 = S= {{1}/{[1,1]}}/S\) , \(F= {{1}/{[1,1]}}/S + ( {{1}/{[0.4,0.7]}}/A+{{1}/{[0.3,0.6]}}/S)\) and the transition function \(\delta \) is define as:

$$\begin{aligned} \delta (S,a)= & {} {{1}/{[0.1,0.2]}}/S + {{1}/{[0.3,0.7]}}/A,\\ \delta (A,a)= & {} {{1}/{[0.5,0.7]}}/A + {{1}/{[0.3,0.4]}}/B,\\ \delta (B,a)= & {} {{1}/{[0.7,0.9]}}/S , \end{aligned}$$

if \(w=aaa\), the transition steps of w in M are as follows:

\(\delta (S,a) = {{1}/{[0.1,0.2]}}/S + {{1}/{[0.3,0.7]}}/A.\)

$$\begin{aligned} \delta ^*(S, aa)= & {} {{1}/{[0.1,0.2]}}.\delta (S,a) \cup {{1}/{[0.3,0.7]}}.\delta (A,a)\\= & {} {{1}/{[0.1,0.2]}}.({{1}/{[0.1,0.2]}}/S + {{1}/{[0.3,0.4]}}/A)\\&\cup ~ {{1}/{[0.3,0.7]}}.( {{1}/{[0.5,0.7]}}/A + {{1}/{[0.3,0.4]}}/B)\\= & {} {{1}/{[0.1,0.2]}}/S + {{1}/{[0.1,0.2]}}/A \\&\cup ~ {{1}/{[0.3,0.7]}}/A + {{1}/{[0.3,0.4]}}/B\\= & {} {{1}/{[0.1,0.2]}}/S + {{1}/{[0.3,0.7]}}/A + {{1}/{[0.3,0.4]}}/B.\\ \delta ^*(S, aaa)= & {} {{1}/{[0.1,0.2]}}.\delta (S,a) \cup {{1}/{[0.3,0.7]}}.\delta (A,a)\\&\cup ~ {{1}/{[0.3,0.4]}}.\delta (B,a)\\= & {} {{1}/{[0.1,0.2]}}.({{1}/{[0.1,0.2]}}/S + {{1}/{[0.3,0.7]}}/A) \\&\cup ~ {{1}/{[0.3,0.7]}}.({{1}/{[0.1,0.2]}}/S + {{1}/{[0.3,0.7]}}/A)\\&\cup ~{{1}/{[0.3,0.4]}}.( {{1}/{[0.7,0.9]}}/S)\\= & {} {{1}/{[0.1,0.2]}}/S + {{1}/{[0.3,0.7]}}/A \\&\cup ~{{1}/{[0.1,0.2]}}/S + {{1}/{[0.3,0.7]}}/A \cup {{1}/{[0.3,0.4]}}/S\\= & {} {{1}/{[0.3,0.4]}}/S + {{1}/{[0.3,0.7]}}/A\\ \delta ^*(S, aaa)\cap F= & {} ({{1}/{[0.3,0.4]}}/S + {{1}/{[0.3,0.7]}}/A \cap {{1}/{[0.3,0.6]}}/S \\&+~ {{1}/{[0.4,0.7]}}/A) \\= & {} {{1}/{[0.3,0.4]}}/S + {{1}/{[0.3,0.7]}}/A \end{aligned}$$

The degree to which string aaa of value is accepted by M is

$$\begin{aligned} L(M, aaa)= & {} height (\delta ^*(S, aaa) \cap F)\\= & {} height ({{1}/{[0.3,0.4]}}/S + {{1}/{[0.3,0.7]}}/A)\\= & {} {{1}/{[\vee \{0.3,0.3\}, \vee \{ 0.4, 0.7\}]}}\\= & {} {{1}/{[0.3, 0.7]}} \end{aligned}$$

Theorem 3.3

Let \(M=(Q, X, \delta , q_0, F)\) be an IT2 FA, then there exists an IT2 regular grammar \(G=(N, T, P, S)\) such that \(L(G) = L(M)\).

Proof

We can construct an IT2 regular grammar \(G=(N, T, P, S)\) ,where \(T = X, N = Q\cup {S} \). The production rules in P is defined as follows:

  1. 1.

    For each \(\delta (A,u)(B) \ne 0\) then \(A {\overset{\rho _1}{\rightarrow }}uB \in P\) such that \(\rho _1 = \delta (A,u)\);

  2. 2.

    If \(\delta (A,u)(B) \ne 0 \) and \( F(B) \ne 0\), then \(A {\overset{\rho _2}{\rightarrow }}u \in P\), such that \(\rho _2 = height_{B \in Q} (\delta (A,u) \cap F(B))\) ;

  3. 3.

    If \(\delta (A,u)(B) \ne 0 \) and \( q_0(A) \ne 0\), then \(S {\overset{\rho _3}{\rightarrow }}uB \in P\), such that \(\rho _3 =(\delta (A,u);\)

  4. 4.

    If \(\delta (A,u)(B) \ne 0 \) , \(q_0(A) \ne 0 \)and \( F(B) \ne 0\), then \(S {\overset{\rho _4}{\rightarrow }}u \in P \), such that \(\rho _4 = height_{B \in Q} (\delta (A,u) \cap F(B))\).

We will show that \(L(G) = L(M)\). Let \(w\in T^*\), then there are two cases for w.

  1. 1.

    If \(w= \Lambda \) then \(L(G)(w) = \rho (S \rightarrow \Lambda ) = L(M)(w)\) .

  2. 2.

    When \(w \ne \Lambda \), let \(w = u_1u_2u_3...u_n\), where \(u_i \in T\) for \(i = 1,2,..., n\). If \(S {\overset{\rho }{\Longrightarrow }}^* w\) there must exist some derivation of w with the form

    $$\begin{aligned} S&{\overset{\rho _1}{\Longrightarrow }}&u_1~A_1\\&{\overset{\rho _2}{\Longrightarrow }}&u_1u_2~A_2\\&{\overset{\rho _3}{\Longrightarrow }}&\ldots \ldots \ldots \\&{\overset{\rho _{n-1}}{\Longrightarrow }}&u_1u_2 \ldots u_{n-1}~A_{n-1}\\&{\overset{\rho _n}{\Longrightarrow }}&u_1u_2 \ldots u_{n-1}u_n\\= & {} w \end{aligned}$$

where \(A_{i-1}{\overset{\rho _i}{\Longrightarrow }} u_iA_i \in P\) for \(i = 1, 2, ..., n\) and \(A_0 =S\), \(A_n = u_n\) with \( \rho = \rho _1 \cap \rho _2\cap \rho _3\cap ... \cap \rho _n.\) From the definition of P, we know that

$$\begin{aligned} L(M)(w)= & {} height~(\delta ^*( S,w)\cap F)\\\supseteq & {} height(\delta (S, u_1)(A_1)\wedge \delta (A_1, u_2)(A_2)\wedge ... \delta (A_{n-1}, u_n)(A_n) \\&\cap F(A_n)) \\= & {} \rho _1 \cap \rho _2 \cap ....\cap \rho _n\\= & {} \rho . \end{aligned}$$

Hence, we have shown that \(L(G, w) \subseteq L(M, w)\) for any \(w \in X^*\), that is \(L(G)\subseteq L(M)\) Conversely, if

$$\begin{aligned} L(M)(w)= & {} height(\delta ^*( S,w)\cap F)\\= & {} height_{A_1,...,A_n \in Q}(\delta (S, u_1)(A_1)\wedge \delta (A_1, u_2)(A_2)\wedge ... \wedge \\&\delta (A_{n-1}, u_n)(A_n) \cap F(A_n)) \\\supseteq & {} height(\delta (S, u_1)(A_1)\wedge \delta (A_1, u_2)(A_2)\wedge ...\wedge \\&height_{A_n\in Q} \delta (A_{n-1}, u_n)(A_n) \cap F(A_n)) \end{aligned}$$

For any \(A_1,...,A_n \in Q,\) let height \((\delta (S, u_1)(A_1)\wedge \delta (A_1, u_2)(A_2)\wedge ...\wedge \) \(height_{A_n\in Q} \delta (A_{n-1}, u_n)(A_n) \cap F(A_n) = \rho _1 \cap \rho _2 \cap \rho _3 \cap ... \cap \rho _n = \rho ,\) then there exists corresponding derivation \( S {\overset{\rho }{\Longrightarrow }}^* w\). Thus it shows that if \(\rho \subseteq L(M)(w)\), then \(\rho \subseteq L(G)(w)\), that is \(L(M)(w) \subseteq L(G)(w)\) for any \(w \in X^*,\) that is \(L(M) \subseteq L(G)\) . Therefore \(L(G) = L(M)\), that is the languages accepted by IT2 fuzzy automata are IT2 regular languages.

Example 3.4

Let \(M= (Q,X, \delta , q_0, F)\) be the IT2 FA in Example 3.1. An equivalent IT2 fuzzy regular grammar \(G = (N, T, P, S)\) is constructed as follows, where \(T \!=\! X \!=\! \{a,b\}, N \!=\! Q \cup \{S\} , S= q_0,\) and production \(P = \{ S \xrightarrow {{1}/ {[0.4, 0.6]}} a q_1, q_1 \xrightarrow {{1}/ {[0.7, 0.9]}} a q_1, q_1 \xrightarrow {{1}/ {[0.3, 0.4]}} a q_2, q_2 \xrightarrow {{1}/ {[0.5, 0.7]}} a q_2, q_1 \xrightarrow {{1}/ {[0.3, 0.4]}} b q_1, q_1 \xrightarrow {{1}/ {[0.4, 0.6]}} b q_2,\}\)

If \(w=aaab\), the derivations of w in G are as follows:

  1. 1.

    \( S \xrightarrow {{1}/{[0.3,0.5]}} a q_1 \xrightarrow {{1}/{[0.7,0.9]}} a q_1 \xrightarrow {{1}/{[0.7,0.9]}} a q_1 \xrightarrow {{1}/{[0.3,0.4]}} b q_1\),

  2. 2.

    \( S \xrightarrow {{1}/{[0.3,0.5]}} a q_1 \xrightarrow {{1}/{[0.7,0.9]}} a q_1 \xrightarrow {{1}/{[0.7,0.9]}} a q_1 \xrightarrow {{1}/{[0.4,0.6]}} b q_2\),

  3. 3.

    \( S \xrightarrow {{1}/{[0.3,0.5]}} a q_1 \xrightarrow {{1}/{[0.7,0.9]}} a q_1 \xrightarrow {{1}/{[0.3,0.4]}} b q_2 \xrightarrow {{1}/{[0.2,0.5]}} b q_1\),

  4. 4.

    \( S \xrightarrow {{1}/{[0.3,0.5]}} a q_1 \xrightarrow {{1}/{[0.7,0.9]}} a q_1 \xrightarrow {{1}/{[0.3,0.4]}} b q_2 \xrightarrow {{1}/{[0.7,0.8]}} b q_2\),

  5. 5.

    \( S \xrightarrow {{1}/{[0.3,0.5]}} a q_1 \xrightarrow {{1}/{[0.3,0.4]}} a q_2 \xrightarrow {{1}/{[0.5,0.7]}} a q_2 \xrightarrow {{1}/{[0.2,0.5]}} b q_1\),

  6. 6.

    \( S \xrightarrow {{1}/{[0.3,0.5]}} a q_1 \xrightarrow {{1}/{[0.3,0.4]}} a q_2 \xrightarrow {{1}/{[0.5,0.7]}} a q_2 \xrightarrow {{1}/{[0.7,0.8]}} b q_2\),

Thus

$$\begin{aligned} L(G)(w)= & {} height\{{1}/{[0.3,0.5]} \cap {{1}/{[0.7,0.9]}} \cap {{1}/{[0.7,0.9]}} \cap {{1}/{[0.3,0.4]}},\\&{{1}/{[0.3,0.5]}} \cap {{1}/{[0.7,0.9]}} \cap {{1}/{[0.7,0.9]}} \cap {{1}/{[0.4,0.6]}},\\&{{1}/{[0.3,0.5]}} \cap {{1}/{[0.7,0.9]}} \cap {{1}/{[0.3,0.4]}} \cap {{1}/{[0.2,0.5]}},\\&{{1}/{[0.3,0.5]}} \cap {{1}/{[0.7,0.9]}} \cap {{1}/{[0.3,0.4]}} \cap {{1}/{[0.7,0.8]}},\\&{{1}/{[0.3,0.5]}} \cap {{1}/{[0.3,0.4]}} \cap {{1}/{[0.5,0.7]}} \cap {{1}/{[0.2,0.5]}},\\&{{1}/{[0.3,0.5]}} \cap {{1}/{[0.3,0.4]}} \cap {{1}/{[0.5,0.7]}} \cap {{1}/{[0.7,0.8]}}\}\\= & {} height \{ {{1}/{[0.3,0.4]}},{{1}/{[0.3,0.5]}},{{1}/{[0.2,0.4]}},{{1}/{[0.3,0.4]}},\\&{{1}/{[0.2,0.4]}},{{1}/{[0.3,0.4]}}\}\\= & {} {{1}/{[\vee \{0.3,0.3, 0.2,0.3,0.2, 0.3\}, \vee \{ 0.4, 0.5,0.4,0.4, 0.4,0.4\}]}}\\= & {} {{1}/{[0.3, 0.5]}} \end{aligned}$$

Finally, in the light of Propositions 3.2 and 3.3, we have following two corollaries.

Corollary 3.1

IT2 fuzzy regular grammars are equivalent to IT2 fuzzy automata.

Corollary 3.2

IT2 fuzzy automata are equivalent to IT2 fuzzy weak regular grammars.

4 IT2 fuzzy language characterize by IT2 fuzzy automata

An IT2 fuzzy language L is an IT2 fuzzy subset of \(X^*\) which is defined in Definition 2.9. In this section, we shall investigate the closure properties of IT2 fuzzy languages recognized by IT2 fuzzy automata.

Definition 4.1

Let \(L_1, L_2\in IT2F(X^*)\). Then \(\forall w\in X^*\)

  1. (1)

    the union of \(L_1\) and \(L_2\), denoted by \(L_1 \cup L_2\), defined as \(L_1 \cup L_2=\frac{1}{[\underline{\mu }_{L_1}(w)\vee \underline{\mu }_{L_2}(w), \overline{\mu }_{L_1}(w)\vee \overline{\mu }_{L_2}(w)]}\),

  2. (2)

    the intersection of \(L_1\) and \(L_2\), denoted by \(L_1 \cap L_2\), defined as \(L=L_1 \cap L_2=\frac{1}{[\underline{\mu }_{L_1}(w)\wedge \underline{\mu }_{L_2}(w), \overline{\mu }_{L_1}(w)\wedge \overline{\mu }_{L_2}(w)]}\),

  3. (3)

    the complement of L, denoted by \(L^C\), defined as \(L^C =\frac{1}{[1-\overline{\mu }_{L_1}(w), 1-\underline{\mu }_{L_1}(w)]}\),

  4. (4)

    the concatenation of \(L_1\) and \(L_2\), denoted by \(L_1 \cdot L_2\), defined as \(L=L_1 \cdot L_2=\frac{1}{[\vee \{\wedge \{\underline{\mu }_{L_1}(u), \underline{\mu }_{L_2}(v)\}\}, \vee \{\wedge \{\overline{\mu }_{L_1}(u), \overline{\mu }_{L_2}(v)\}\}]}\), where \(w=uv\),

  5. (5)

    the Kleene closure of L, denoted by \(L^*\), defined as \(\tilde{L}^*=\bigcup _{i=0}^{\infty }L^i=L^0\cup L^1\cup L^2\cup ...\), where

    $$\begin{aligned} L^0 =\left\{ \begin{array}{ll} 1/[1, 1] &{} { x=\Lambda }\\ 1/[0, 0] &{} {x \not = \Lambda }\\ \end{array} \right. \end{aligned}$$

Theorem 4.1

Let \(M_1\) and \(M_2\) be two IT2 FAs. Then there exists an IT2 FA M such that

$$\begin{aligned} L(M) = L(M_1) \cup L(M_2). \end{aligned}$$

Proof

Let \(L(M_1)\) and \(L(M_2)\) be the IT2 fuzzy automata languages accepted by IT2 FAs \(M_1 = (Q_1, X_1, \delta _1, q_{0_1}, F_1)\) and \(M_2 = (Q_2, X_2, \delta _2, q_{0_2}, F_2)\) respectively. Then we define an IT2 FA \(M=(Q, X, \delta , q_0, F)\) as follows

$$\begin{aligned} Q= & {} Q_1 \cup Q_2, ~~where ~~Q_1 \cap Q_2 = \emptyset ,\\ F(q_i)= & {} \left\{ \begin{array}{ll} F_1(q_i) &{} \text{ if } q_i \in Q_1\text{, }\\ F_2(q_i) &{} \text{ if } q_i \in Q_2\text{; } \end{array} \right. \\ \delta (q_i, a)= & {} \left\{ \begin{array}{ll} \delta _1(q_i,a) &{} \text{ if } \quad q_i \in Q_1,\\ \delta _2(q_i,a) &{} \text{ if } \quad q_i \in Q_2,\\ 1/[0,0] &{} \text{ otherwise }; \end{array} \right. \end{aligned}$$

and

$$\begin{aligned} \delta ^* (q_i, w)(q_j) =\left\{ \begin{array}{ll} \delta _1^*(q_i,w)(q_j) &{} \text{ if } \quad q_i, q_j \in Q_1, \\ \delta _2^*(q_i,w)(q_j) &{} \text{ if } \quad q_i, q_j \in Q_2,\\ 1/[0,0] &{} \text{ otherwise } \end{array} \right. \end{aligned}$$

Therefore, \(\forall w\in X^*\), \(L(M, w)=height[\delta ^*(q_0, w)\cap F]=height[\{\delta _1^*(q_0, w)\cap F_1\}\vee \{\delta _2^*(q_0, w)\cap F_2\}]=height[\delta _1^*(q_0, w)\cap F_1]\vee height[\delta _2^*(q_0, w)\cap F_2]=L(M_1, w)\vee L(M_2, w)\). Hence \(L(M) = L(M_1) \cup L(M_2)\).

Theorem 4.2

Let \(M_1\) and \(M_2\) be two IT2 FAs. Then there exists an IT2 FA M such that

$$\begin{aligned} L(M) = L(M_1) \cap L(M_2). \end{aligned}$$

Proof

Let \(L(M_1)\) and \(L(M_2)\) be the IT2 fuzzy automata languages accepted by IT2 FAs \(M_1 = (Q_1, X_1, \delta _1, q_{0_1}, F_1)\) and \(M_2 = (Q_2, X_2, \delta _2, q_{0_2}, F_2)\) respectively. Then we define an IT2 FA \(M=(Q, X, \delta , q_0, F)\) as follows

$$\begin{aligned}&Q = Q_1 \times Q_2 ~( direct~ product ~of~ Q_1~ and~ Q_2),\\&F= F_1 \cap F_2,\\&\delta ((q_i\times q_j),(a.b)) = \delta _1(q_i,a) \wedge \delta _2(q_j,b), ~(q_i, q_j) \in Q_1 \times Q_2, \end{aligned}$$

and

$$\begin{aligned} \delta ^*((q_{i}, q_{j}) (x,y)) (p_{i}, p_{j})=\delta _1^*(q_{i},x)(p_{i})\wedge \delta _2^*(q_{j}, y)(p_{j}), \end{aligned}$$

\(\forall (q_{i}, q_j)\in Q_1 \times Q_2, (p_{i}, p_j)\in Q_1 \times Q_2\).

Therefore, \(\forall w\in X^*\), \(L(M, w)=height[\delta ^*(q_0, w)\cap F]=height[\delta _1^*(q_0, w)\cap F_1 \cap \delta _2^*(q_0, w)\cap F_2]=height[\delta _1^*(q_0, w)\cap F_1]\wedge height[\delta _2^*(q_0, w)\cap F_2]=L(M_1, w)\wedge L(M_2, w)\). Hence \(L(M) = L(M_1) \cap L(M_2)\).

Theorem 4.3

Let \(M_1\) and \(M_2\) be two IT2 FAs. Then there exists an IT2F automaton M such that

$$\begin{aligned} L(M)= L(M_1)\cdot L(M_2). \end{aligned}$$

Proof

Let \(L(M_1)\) and \(L(M_2)\) be the IT2 fuzzy automata languages accepted by IT2 FAs \(M_1 = (Q_1, X_1, \delta _1, q_{0_1}, F_1)\) and \(M_2 = (Q_2, X_2, \delta _2, q_{0_2}, F_2)\) respectively. Then we define an IT2 FA \(M=(Q, X, \delta , q_0, F)\) as follows

$$\begin{aligned} Q= & {} Q_1 \cup Q_2,~ where ~~Q_1 \cap Q_2 = \emptyset ,\\ F= & {} FF =F^2 \end{aligned}$$

and

Therefore, . Hence \(L(M) = L(M_1)\cdot L(M_2)\).

Following result can be prove easily by using Propositions 4.1 and 4.3.

Theorem 4.4

Let \(M_1\) and \(M_2\) be two IT2 FAs. Then

$$\begin{aligned} L(M_1)= L(M_2)^*. \end{aligned}$$

Definition 4.2

Let M be an IT2 FA and \(\lambda =1/\left[ \underline{\lambda }, \overline{\lambda }\right] \), \(\left[ \underline{\lambda }, \overline{\lambda }\right] \in Int([0,1])\), set of all closed subintervals of [0, 1]. Then a \(\lambda \)-IT2 fuzzy language accepted by M with parameter \(\lambda \) is defined as

$$\begin{aligned} L(M; \lambda )=\{x: L_M(x)\supseteq \lambda , x\in X^*\} \end{aligned}$$

Theorem 4.5

Let M be an IT2 FA and \(L(M;\lambda )\) a \(\lambda \)-IT2 fuzzy language accepted by M. Then \(L(M;\lambda )\) is not closed under IT2 fuzzy complement.

Proof

Let M be an IT2 FA and \(L(M;\lambda )\) a \(\lambda \)-IT2 fuzzy language accepted by M. Then we have \(L(M;\lambda _1)\supseteq L(M;\lambda _2)\) if \(\lambda _1 \le \lambda _2\). That is \(L(M;\lambda )\) is non-increasing for \(\lambda \). On the other hand, if \(\lambda _1 \le \lambda _2\), then \(L^C(M;\lambda _1)\subseteq L^C(M;\lambda _2)\) and thus \(L^C(M;\lambda )\) is non-decreasing, a contradiction appears.

Following example illustrate the fact of the above proposition.

Example 4.1

Consider Example 2.1, where \(L(M,aa)=height(\delta (q_0,aa)\cap F)=1/[0.3,0.4]\), \(L(M, aaa)=height(\delta (q_0,aaa)\cap F)=1/[0.3,0.4]\) and

\(L(M, aaab)=height(\delta (q_0,aa)\cap F)=1/[0.3,0.5]\). Let \(\lambda _1=1/[0.2, 0.4]\) and \(\lambda _2=1/[0.3, 0.5]\) such that \(\lambda _1\le \lambda _2\). Then by the Definition 4.2, we have \(L(M; \lambda _1)=\{aa, aaa, aaab\}\) and \(L(M; \lambda _2)=\{aaab\}\). Thus \(L(M; \lambda _1) \supseteq L(M; \lambda _2)\). On the other hand, \(L^C(M, aa)=1/[0.7,0.6]\), \(L^C(M, aaa)=1/[0.7,0.6]\) and \(L^C(M, aaab) =1/[0.7,0.5]\). Therefore \(L^C(M; \lambda _1) \subseteq L^C(M; \lambda _2)\) if \(\lambda _1 \le \lambda _2\), and thus a contradiction appears.

5 Conclusion

In this paper, we have proposed the concept of IT2 fuzzy grammar and established their relationship with IT2 fuzzy automata. In particular, we obtained that an IT2 fuzzy weak regular grammars are equivalent to IT2 fuzzy regular grammars, and if an IT2 fuzzy language is generated by an IT2 fuzzy grammar, it can be accepted by an IT2 fuzzy automata, and vice versa. Furthermore, we obtained some important operations on IT2 fuzzy languages and show that IT2 fuzzy languages recognized by IT2 fuzzy automata is closed under the operations of union, intersection, concatenation and Kleene closure but are not closed under complement. We hope that, like fuzzy grammar, IT2F grammar which is another dimension of application IT2 fuzzy set theory, will attract the researchers and the work initiated here will help in finding some successful application of IT2F grammar, as done for T2 fuzzy grammar in [1]. Much more can be further done by introducing the concepts of their primaries and decomposition (as done, e.g., in [27]). It may also be worthwhile to try using topological and categorical methods in the study of IT2 fuzzy automata, as done for fuzzy automata in, e.g, [26].