Verificando se a união de dois idiomas é regular
-
29-09-2020 - |
Pergunta
Como verificar se
$ l={c ^ ka ^ nb ^ n \ meados k> 0 \ wedge n \ geqslant0} \ copo \ {a, b} ^ * $ <
é regular, onde
$ l_1= {c ^ ka ^ nb ^ n \ meados k> 0 \ wedge n \ geqslant0} $ é claramente não regular e $ l_2= {a, b \} ^ * $ é ...?
Solução
Se $ l $ eram regulares do que assim a seguinte linguagem seria: $$ l \ cap CA ^ * b ^ *= \n^ n ^ n \ mid n \ geq 0 \}. $$ Você pode mostrar que a última linguagem não é regular de várias maneiras.
Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange