questes_automatos

Prévia do material em texto

obs: O alfabeto de todas as linguagens nas questões abaixo é o Σ = {0, 1}.
1. Para cada linguagem abaixo, determine um AFD que a reconheça:
a. L = {w | w contém exatamente um śımbolo 1}
b. L = {w | w contém pelo menos dois śımbolos 1}
c. L = {w | w contém a subcadeia 10}
d. L = {w | w não contém a subcadeia 10}
2. Para cada linguagem abaixo, determine um AFN que a reconheça:
a. L = {w | w inicia com o śımbolo 1 ou acaba com o śımbolo 0}
b. L = {w | w = 00y para alguma subcadeia y}
c. L = {w | w contém a subcadeia 1010}
d. L = {w | w contém uma quantidade par de śımbolos 0 e ı́mpar de śımbolos 1}
1