a) Defina uma gramática regular.
b) Defina uma linguagem regular.
c) Mostre que o conjunto
é uma linguagem regular.
b) Defina uma linguagem regular.
c) Mostre que o conjunto
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
a) dar a definição de gramática regular;
b) dar a definição de linguagem regular;
c) mostrar que
é uma linguagem regular.
O conteúdo é Teoria de Linguagens Formais, e vamos usar definições de gramáticas, expressões regulares e autômatos.
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
cujas produções em
obedecem a um dos três formatos abaixo, com
e
:
,
,
.
Ou seja, cada lado direito tem no máximo um símbolo terminal seguido opcionalmente de um não-terminal, ou é o vazio.
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
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.
– 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
é regular, basta exibir uma expressão regular que gere exatamente
. A expressão
gera todas as cadeias de zeros seguidos de uns, isto é, primeiro um bloco de
zeros
e depois um bloco de
uns
, com
. Logo
e, por definição, toda linguagem de uma expressão regular é regular.
Resposta
(a) Uma gramática regular é um sistema
em que cada produção tem o formato
ou
,
com e
.
com
(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
é gerado pela expressão regular
, logo é uma linguagem regular.