Atividade de Linguagens Formais e Autômatos

Atividade de Linguagens Formais e Autômatos – Lista 03
Larissa Rafaela Silva¹ Engenharia da Computação – 5º Período – Fundação Educacional de Divinópolis (FUNEDI) Caixa Postal 35501-170 – Divinópolis – MG – Brasil

1)
Descreva os conjuntos denotados pelas expressões regulares sobre o alfabeto =
{0,1}.
a- 0 | 10* b- (0 | 1)0* c- (0011)* d- (0 | 1)* 1(0 | 1)* e- 0*11*0 f- 0(0 | 1)*0 g- * h- (| 0) (| 1) i- (000* | 1)* j- ( 0* | 0*11 (1 | 00*11)*) (| 00* )

a) Linguagem que se inicia com 0 ou 1, seguida de n 0 (zeros). b) Linguagem que se inicia com 0 ou 1, seguida de n 0 (zeros). c) Linguagem onde é aceito vazio ou 0011 N vezes. d) Linguagem onde é aceito 1 como subpalavra. e) Linguagem que começa com N 0, seguido de 1, seguido de N 1, terminada com 0. f) Linguagem que começa com 0, seguido de 0 ou 1 N vezes , terminada com 0. g)Linguagem aceita vazio. h)Linguagem aceita vazio, ou 0 seguido de 1. i) Linguagem que começa com 00, onde pode ser seguido de N 0 ou 1 N vezes. j) 0 N vezes ou 0 N vezes seguido de 11 seguido de 1 ou 0 N>0 vezes seguido de 11 N vezes, seguido de lambda ou N>0 vezes

Determine para cada linguagem sobre o alfabeto = {0,1} abaixo, uma expressão regular que a denote. Admita a convenção | x |0 como sendo o número de símbolos 0 que ocorrem na cadeia x *. a- {0} * {1} b- * {01} c- { x * | | x |0 3} d- { x * | | x |1 é par} e- { x * | x não possui dois 0’s e não possui dois 1’s consecutivos}

a) Linguagem com prefixo 0, substring poderá ser qualquer coisa,tendo sufixo 1 = 0(0|1)*1

b) Linguagem com sufixo 01. (0|1)*01

c) Linguagem aceita qualquer sequência na qual possua um numero de zeros igual ou maior que 3.( 0|1)*0+(0|1)*0+(0|1)*0+(0|1)*

d) Linguagem aceita qualquer sequencia que tenha uma substring de pares de 1 (0|11)*

e) Linguagem aceita qualquer sequência de 0 ou 1, na qual os mesmos não podem ser consecutivos . Aceita vazio.