Ed
ano passado
Para identificar qual das linguagens apresentadas é não regular, vamos analisar cada uma das opções: A. L1 = {w | w inicia com b e termina com a} - Esta linguagem é regular, pois pode ser descrita por uma expressão regular. B. L2 = {w | w possui um número par de a e b} - Esta linguagem é não regular, pois requer que o número de 'a's e 'b's seja par, o que não pode ser reconhecido por um autômato finito. C. L3 = {w | w possui aa ou bb como subcadeia} - Esta linguagem é regular, pois pode ser descrita por uma expressão regular. D. L4 = {w | w possui aaa como sufixo} - Esta linguagem é regular, pois pode ser reconhecida por um autômato finito. E. L5 = {w | w possui um número de a's igual ao número de b's} - Esta linguagem é não regular, pois também requer que o número de 'a's e 'b's seja igual, o que não pode ser reconhecido por um autômato finito. Portanto, as opções B e E são não regulares, mas como a pergunta pede para marcar uma opção, a mais clássica e frequentemente citada em contextos de linguagens não regulares é: B. L2 = {w | w possui um número par de a e b}.
Cadastre-se ou realize login
Ed
há 2 anos
Para identificar uma linguagem que não é regular, podemos aplicar o lema do bombeamento para linguagens regulares. Esse lema afirma que, se uma linguagem é regular, então existe um número p (chamado de "pumping length") onde qualquer palavra w na linguagem com comprimento maior ou igual a p pode ser dividida em três partes, w = xyz, que satisfazem três condições: 1. Para todo i ≥ 0, xy^iz está na linguagem. 2. |y| > 0. 3. |xy| ≤ p. Vamos analisar as opções: A. L1 = {w | w inicia com b e termina com a} Essa linguagem é regular, pois pode ser representada por uma expressão regular simples: b(a+b)*. B. L2 = {w | w possui um número de par de a e b} Essa linguagem é regular, pois pode ser representada por uma expressão regular: (aa)*(bb)*. C. L3 = {w | w possui aa ou bb como subcadeia} Essa linguagem é regular, pois pode ser representada por uma expressão regular: (a+b)*(aa+bb)(a+b)*. D. L4 = {w | w possui aaa como sufixo} Essa linguagem é regular, pois pode ser representada por uma expressão regular: (a+b)*aaa. E. L5 = {w | w possui um número de a's igual ao número de b's} Essa linguagem não é regular, pois não pode ser representada por uma expressão regular devido à necessidade de contar o número de a's e b's, o que não é possível em uma máquina de estados finitos. Portanto, a opção correta é: E. L5 = {w | w possui um número de a's igual ao número de b's}.
Mais perguntas desse material