A LISTA DE GRAMÁTICA REGULAR

Ministério da Educação Universidade Tecnológica Federal do Paraná

Câmpus Medianeira

Disciplina : Linguagens Formais e Autômatos PR

UNIVERSIDADE TECNOLÓGICA FEDERAL DO PARANÁ

Trabalho Gramática Regular

Eliezer Schlickmann

1. Construa gramáticas regulares que geram as seguintes linguagens, considerando o alfabeto Σ = {a, b}

a) { w ∈ Σ* | w termine com a subcadeia “bab”}

{s, a,b}

S->bab

S->aS

S->bS

b) { w ∈ Σ* | |w| >= 3 }

{S, A, B, C, a,b}

S->aS

S->bS

S->A

A->aB

A->bB

B->aC

B->bC

C->a

C->b

c) { w ∈ Σ* | |w| é ímpar }

{S, a,b}

S->abS

S->baS

S->bbS

S->aaS

S->a

S->b

d) { w ∈ Σ* | w contenha um número ímpar de símbolos “a” }

{S,A,a,b}

S -> aA

S -> ab

S -> aaS

S -> bS

S -> abaS

A -> bA

A -> aaA

A -> e

e) { w ∈ Σ* | w começa com o símbolo “a” e tem tamanho par }

{S,A,B,a,b}

S -> aA

A -> aB

A -> bB

B -> e

B -> abB

B -> baB

B -> aaB

B -> bbB

f) { w ∈ Σ* | w contenha no mínimo dois símbolos “a” ou exatamente dois símbolos “b” }

{S,A,B,C,D,a,b}

S -> aA

S -> bS

A -> aA

A -> bA

A -> aD

D -> e