a) Defina uma gramática regular.
b) Defina uma linguagem regular.
c) Mostre que o conjunto \left\{0^{m} 1^{n} \mid m, n=0,1,2, \ldots\right\} é uma linguagem regular.

Passo 1

O enunciado pede três coisas:
a) dar a definição de gramática regular;
b) dar a definição de linguagem regular;
c) mostrar que
L = \{0^{m}1^{n}\mid m,n=0,1,2,\dots\}
é uma linguagem regular.
O conteúdo é Teoria de Linguagens Formais, e vamos usar definições de gramáticas, expressões regulares e autômatos.

Passo 2

Uma gramática regular é uma gramática G=(V,\Sigma,P,S) cujas produções em P obedecem a um dos três formatos abaixo, com A,B\in V e a\in\Sigma: A\to aB, A\to a, A\to \epsilon.
Ou seja, cada lado direito tem no máximo um símbolo terminal seguido opcionalmente de um não-terminal, ou é o vazio.

Passo 3

Uma linguagem regular é uma linguagem L\subseteq\Sigma^* que pode ser descrita de qualquer uma destas formas equivalentes:
– por um autômato finito (determinístico ou não determinístico),
– por uma expressão regular,
– ou por uma gramática regular.

Passo 4

Para mostrar que
L = \{0^{m}1^{n}\mid m,n\ge0\}
é regular, basta exibir uma expressão regular que gere exatamente L. A expressão
0^*1^*
gera todas as cadeias de zeros seguidos de uns, isto é, primeiro um bloco de m zeros 0^* e depois um bloco de n uns 1^*, com m,n\ge0. Logo
L = L(0^*1^*)
e, por definição, toda linguagem de uma expressão regular é regular.

Resposta

(a) Uma gramática regular é um sistema G=(V,\Sigma,P,S) em que cada produção tem o formato \;A\to aB,\;A\to a ou \;A\to \epsilon,
com A,B\in V e a\in\Sigma.
(b) Uma linguagem é regular se é reconhecida por um autômato finito, ou equivalentemente se pode ser descrita por uma expressão regular ou gerada por uma gramática regular.
(c) O conjunto \{0^{m}1^{n}\mid m,n\ge0\} é gerado pela expressão regular 0^*1^*, logo é uma linguagem regular.

Exercícios de Livros Relacionados