Esta linguagem é regular ou não?

Question

Eu tenho o idioma {4^(w⋅g)34^(g)|w,g∈NAT} sobre o alfabeto {0,1}.

Preciso descobrir se esta linguagem é reconhecível, decidível, livre de contexto, regular ou nada disso.

Como eu faria isso ou saberia?

Obrigado

Answer 1

Considere qualquer string do formato 4^a 3 4^b.Podemos encontrar w, g para nós a, b?Bem, nós sabemos disso g deve ser igual b, e então podemos escolher w = a + g.Desde a, b e g são números naturais, então também devem ser w;a resposta é que, sim, para qualquer string no formato 4^a 3 4^b, temos uma string no seu idioma.

A linguagem de todas as strings do formulário 4^a 3 4^b é descrito pela expressão regular 4* 3 4* e, como tal, a sua linguagem é regular, livre de contexto, decidível e reconhecível.

Suponha que sua linguagem não fosse regular;como você poderia saber?Você poderia usar o teorema de Myhill-Nerode ou o Pumping Lemma para linguagens regulares para derivar uma contradição ao assumir que a linguagem era regular.

Suponha que sua linguagem não fosse livre de contexto.Você poderia usar o Lema do Pumping para linguagens livres de contexto para derivar uma contradição ao assumir que a linguagem era livre de contexto.

É claro que, se a sua linguagem não fosse decidível ou reconhecível, você também poderia provar isso de várias maneiras.