Turmas - 2º Semestre de 2018
Turmas
2º Semestre de 2018

(Ramos, 2009) Uma linguagem formal é um conjunto, finito ou infinito, de cadeias de comprimento finito, formadas pela concatenação de elementos de um alfabeto finito e não-vazio. Analise as seguintes assertivas sobre linguagens formais.

1. A palavra abccba pertence a linguagem formal L = {ω ∈ {a, b, c}* | ω = ω^R e |ω| = 6}.
2. A palavra aabbcc pertence a linguagem formal L = {aⁱb^jc^k | i ≠ j ≠ k}.
3. A palavra abccba pertence a linguagem formal L = {ω ∈ {a, b, c}* | ω = αα^R}.
4. A palavra aabbcc pertence a linguagem formal L = {ω ∈ {a, b, c}* | ω = α²}.

A análise permite concluir que:

a. apenas as assertivas I e II estão corretas.

b. apenas as assertivas I e III estão corretas.

c. apenas as assertivas II e III estão corretas.

d. apenas as assertivas II e IV estão corretas.

e. apenas as assertivas III e IV estão corretas.

As cadeias produzidas pela expressão regular (a* + aa*)(a + ε) podem ser reconhecidas por um autômato finito determinístico, autômato finito não-determinístico ou autômato finito com movimentos vazios, contendo no mínimo:

a. 1 estado

b. 2 estados

c. 3 estados

d. 4 estados

e. 5 estados

(Ramos, 2009) Considere a linguagem L = {ω ∈ {a, b, c, d}*, definida informalmente como segue.

1. Para cada símbolo a presente na cadeia ω, deverá existir uma subcadeia bbb situada imediatamente à direita do mesmo;
2. Para cada símbolo c presente na cadeia ω, a subcadeia situada imediatamente à direita do mesmo deverá ser diferente de bbb.

São exemplos de sentenças pertencentes a linguagem L: cbb, abbbcabbb, bbabbbcbb.

Qual função de transição (δ) corresponde ao autômato finito determinístico que reconheça a linguagem L.

M₂ = ({a, b, c, d}, {q₀, q₁, q₂, q₃, q₄, q₅, q₆}, δ₂, q₀, {q₀, q₄, q₅, q₆})

a.

b.

c.

d.

e.

Como alternativa para a representação dos conjuntos regulares, visando obter maior concisão e facilidade de manipulação, Kleene desenvolveu, na década de 1950, a notação das expressões regulares. Considere a existência de uma expressão regular sobre o alfabeto {a, b, c} a qual represente a maior linguagem que satisfaça simultaneamente às seguintes condições:

1. Cada uma de suas sentenças deve conter exatamente três símbolos a – nem mais, nem menos;
2. O primeiro e o segundo símbolo a de cada sentença devem estar separados por pelo menos um símbolo, que não seja a;
3. O segundo e o terceiro símbolo a de cada sentença devem estar separados por uma quantidade par, diferente de zero, de símbolos que não sejam a.

Qual expressão regular satisfaz as condições exigidas:

a. ER = (b + c)^* a (b + c)^* a (bb + bc + cb + cc)^* a (b + c)^*

b. ER = (b + c)^* a (b + c)⁺ a (bb + bc + cb + cc)⁺ a (b + c)^*

c. ER = a (b + c)⁺ a (bb + bc + cb + cc)⁺ a

d. ER = a (b + c)⁺ a (b + c)+ (b + c)⁺ a

e. ER = a (b + c)⁺ a (b + c)^* a

(Ramos, 2009) Apesar do elevado interesse prático que recai sobre os autômatos finitos determinísticos, uma vez que eles servem como base para a construção de programas extremamente eficientes, do ponto de vista teórico há também um interesse muito grande pelos autômatos finitos não-determinismos, devido à maior facilidade com que eles permitem a demonstração de certos teoremas. Do ponto de vista prático, os autômatos finitos não-determinismos são, muitas vezes, mais intuitivos do que os correspondentes autômatos finitos determinísticos, o que os torna, geralmente, mais adequados para a análise e especificação de linguagens regulares. Considere a linguagem L = {ω ∈ {a, b, c}* | se o primeiro símbolo de ω é a, então o terceiro deve ser b e o último deve ser c}. São sentenças de L: abbacc, acbbbc, cba, aabc. Não são sentenças de L: aaa, abba, aabccb. Desenvolva um autômato finito não-determinístico que reconheça as sentenças da linguagem L.

M₅ = ({a, b, c}, {q₀, q₁, q₂, q₃, q₄, q₅}, δ₅, q₀, {q₄, q₅})

(Ramos, 2009) Da mesma forma como ocorre com as expressões regulares, os autômatos finitos também possibilitam a formalização das linguagens regulares. No entanto, diferentemente daquela notação, que constituem dispositivos de geração de sentenças, os autômatos finitos são dispositivos de aceitação de sentenças. Apresente um autômato finito determinístico equivalente ao autômato finito não-determinístico apresentado a seguir.

M₆ = ({a, b, c}, {q₀, q₁, q₂, q₃, q₄}, δ₆, q₀, {q₀, q₂, q₄})

M_6r = ({a, b, c}, {q₀, q₁, q₂, q₃, q₄, q₅, q₆}, δ_6r, q₀, {q₀, q₂, q₃, q₄})

(Ricarte, 2008) O método da construção de subconjuntos é um procedimento sistemático que converte um autômato finito com movimentos vazios num autômato finito determinístico. O princípio associado a esse método é criar novos estados, no autômato finito determinístico, que estejam associados a todas as possibilidades de estados originais em um dado momento da análise da sentença no processo de reconhecimento. Para cada estado original, essas possibilidades incluem o estado do autômato finito com movimentos vazios e todos os estados que podem ser atingidos a partir dele com transições pela string vazia. Converta, usando o método da construção de subconjuntos, o autômato finito não-determinístico com movimentos vazios apresentado a seguir para um autômato finito determinístico.

M₇ = ({a, b, c}, {q₀, q₁, q₂, q₃, q₄}, δ₇, q₀, {q₄})

M_7r = ({a, b, c}, {q₀, q₁, q₂, q₃, q₄}, δ_7r, q₀, {q₀, q₁, q₂, q₃, q₄})

(Ricarte, 2008) Em geral, a aplicação do método da construção de subconjuntos produz autômatos com estados redundantes, ou seja, estados que poderiam ser combinados em um único estado sem alterar a linguagem que é reconhecida. Minimize, se possível, o número de estados do autômato finito determinístico resultante da Questão 07.

M₈ = ({a, b, c}, {q₀, q₁, q₂}, δ₈, q₀, {q₀, q₁, q₂})