Est-Ce la Langue Ordinaire ou pas?

Question

J'ai la langue {4^(w⋅g)34^(g)|w,g∈NAT} sur l'alphabet {0,1}.

J'ai besoin de savoir si ce langage est reconnaissable, decidable, sans contexte, régulier ou aucune de ces.

Comment pourrais-je aller sur le faire ou savoir?

Merci

Answer 1

Considérons une chaîne de la forme 4^a 3 4^b.Pouvons-nous trouver w, g pour notre a, b?Eh bien, nous savons que g doit être égale à b, et puis on peut choisir w = a + g.Depuis a, b et g sont des nombres naturels, doit donc l'être également w;la réponse est que, oui, pour une chaîne de la forme 4^a 3 4^b, nous avons une chaîne de caractères dans votre langue.

La langue de toutes les chaînes de la forme 4^a 3 4^b est décrit par l'expression régulière 4* 3 4* et, en tant que tel, votre langage est régulier, sans contexte, decidable et reconnaissable.

Supposons que votre langue n'étaient pas régulières;comment pourriez-vous dire?Vous pouvez utiliser le Myhill-Nerode théorème ou le Lemme de Pompage pour les langages réguliers pour en déduire une contradiction d'assumer la langue régulièrement des.

Supposons que votre langue n'est pas libre de tout contexte.Vous pouvez utiliser le Lemme de Pompage pour le contexte-gratuit langues pour en déduire une contradiction d'assumer la langue étaient libre de tout contexte.

Bien sûr, si votre langue n'étaient pas decidable ou reconnaissables, vous pouviez prouver que, dans de diverses façons.