DIM0606 - LINGUAGENS FORMAIS E AUTÔMATOS

Sejam $A$ e $B$ dois conjuntos quaisquer, uma função $f$ de $A$ em $B$, denotado como $f:A\to B$, é uma relação que associa cada elemento de $A$ a, no máximo, um elemento em $B$.

Sejam $A$ e $B$ dois conjuntos quaisquer, e sejam $f$ e $g$ funções de $A$ em $B$, isto é, $f,g:A\to B$. Dizemos que $f$ é uma função parcial quando não está definida para todos os elementos de $A$. Por outro lado, $f$ é uma função total quando está definida para todos os elementos de $A$.

Um alfabeto é um conjunto de símbolos finito e não vazio denotado convencionalmente pelo símbolo $\Sigma$.

Seja $\Sigma$ um alfabeto, qualquer sequência finita de símbolos na forma $a_1\cdots a_n$ com $a_i\in \Sigma$ para todo $1\le i\le n$ é dita uma palavra sobre $\Sigma$.

Seja $w$ uma palavra, o comprimento de $w$, denotado por $\left|w\right|$, é o número de símbolos que compõem $w$.

Seja $w$ uma palavra, $w$ é dita palavra vazia, e denotada por $\lambda$, se, e somente se, $\left|w\right|=0$.

Sejam $w_1=a_1\cdots a_n$ e $w_2=b_1\cdots b_m$ duas palavas quaisquer, a concatenação de $w_1$ com $w_2$, denotada por $w_1{w}_2$ é a palavra formada por todos os símbolos de $w_1$ seguidos por todos os símbolos de $w_2$, ou seja: $$w_1{w}_2=a_1\cdots a_n{b}_1\cdots b_m$$

Seja uma palavra $w$, a palavra potência de $w$, denotada por $w^n$, é definida recursivamente como: $$w^0=\lambda$$ $$w^{n+1}=w{w}^n$$

Seja uma palavra $w=a_1\cdots a_n$, a palavra inversa de $w$, denotada por $w^r$, é tal que $w^r=a_n\cdots a_1$.

Seja um alfabeto $\Sigma$, a potência de $\Sigma$, denotada por ${\Sigma }^n$, é definida recursivamente como: $${\Sigma }^0=\{\lambda \}$$ $${\Sigma }^{n+1}=\{aw\mid a\in \Sigma ,w\in {\Sigma }^n\}$$

Seja $\Sigma$ um alfabeto, o fecho positivo e o fecho de Kleene de $\Sigma$, denotados em ordem por ${\Sigma }^{+}$ e ${\Sigma }^{\ast }$, correspondem, respectivamente, aos conjuntos: $${\Sigma }^{+}=\bigcup _{i=1}^{\infty }{\Sigma }^i\text{ e }{\Sigma }^{\ast }=\bigcup _{i=0}^{\infty }{\Sigma }^i$$

Seja as palavra $w,u,v\in {\Sigma }^{\ast }$, dizemos que $u$ é prefixo de $w$, denotado por $u{\preccurlyeq }_{p}w$, sempre que $w=uv$. Por outro lado, dizemos que $u$ é sufixo de $w$, denotado por $u{\preccurlyeq }_{s}w$, sempre que $w=vu$.

Seja $w\in {\Sigma }^{\ast }$, o conjunto de todos os prefixos de $w$ corresponde ao conjunto: $$PRE\left(w\right)=\{u\in {\Sigma }^{\ast }\mid u{\preccurlyeq }_{p}w\}$$ e o conjunto de todos os sufixo de $w$ corresponde ao conjunto $$SUF\left(w\right)=\{u\in {\Sigma }^{\ast }\mid u{\preccurlyeq }_{s}w\}$$

Dado um alfabeto $\Sigma$, qualquer subconjunto $L\subseteq {\Sigma }^{\ast }$ será chamado de linguagem sobre $\Sigma$.

Sejam as linguagens $L_1,L_2$, a concatenação de $L_1$ e $L_2$, denotado por $L_1{L}_2$, corresponde ao conjunto: $$L_1{L}_2=\{uv\in {\left({\Sigma }_1\cup {\Sigma }_2\right)}^{\ast }\mid u\in L_1,v\in L_2\}$$

Seja $L$ uma linguagem, a linguage m reversa de L, denotada por $L^r$, corresponde ao conjunto: $$L^r=\{w^r\mid w\in L\}$$

Seja uma linguagem $L$, a linguagem potência de $L$, denotada por $L^n$, é definida recursivamente como:
$$L^0=\{\lambda \}$$ $$L^n=L{L}^{n-1}$$

Seja $L$ uma linguagem, o Fecho Positivo e o Fecho de Kleene de L, denotados em ordem por $L^{+}$ e $L^{\ast }$, são, respecivamente: $$L^{+}=\bigcup _{i=1}^{\infty }{L}^i\text{ e }{L}^{\ast }=\bigcup _{i=0}^{\infty }{L}^i$$

Seja $L$ uma linguagem, as linguagens dos prefixos e dos sufixos de $L$, denotadas em ordem por $PRE\left(L\right)$ e $SUF\left(L\right)$, são, respectivamente, os seguintes conjuntos: $$PRE\left(L\right)=\{u\in {\Sigma }^{\ast }\mid u{\preccurlyeq }_p,w\in L\}$$ $$SUF\left(L\right)=\{u\in {\Sigma }^{\ast }\mid u{\preccurlyeq }_s,w\in L\}$$