Is This Language Regular or not?
-
21-12-2019 - |
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
Solution
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.