Is This Language Regular or not?

Question

I have the language {4^(w⋅g)34^(g)|w,g∈NAT} over the alphabet {0,1}.

I need to find out if this language is recognizable, decidable, context free, regular or none of these.

How would i go about doing that or knowing?

Thanks

Answer 1

Consider any string of the form 4^a 3 4^b. Can we find w, g for our a, b? Well, we know that g must equal b, and then we can choose w = a + g. Since a, b and g are natural numbers, so too must be w; the answer is that, yes, for any string of the form 4^a 3 4^b, we have a string in your language.

The language of all strings of the form 4^a 3 4^b is described by the regular expression 4* 3 4* and, as such, your language is regular, context free, decidable and recognizable.

Suppose your language weren't regular; how could you tell? You could use the Myhill-Nerode theorem or the Pumping Lemma for regular languages to derive a contradiction from assuming the language were regular.

Suppose your language weren't context-free. You could use the Pumping Lemma for context-free languages to derive a contradiction from assuming the language were context-free.

Of course, if your language weren't decidable or recognizable, you could prove that in various ways as well.