Given the alphabet $\Sigma=\{a, b\}$ and for the next Language $L=\{w:|w|_a=2^n+273\text{ for }n\in \mathbb{N}\}$ determine whether the language is regular.
Firstly, I think this language is regular. And i was thinking about two options of solving this one, But i'm not not sure if i use them correctly.
Lets say i wanna write a regular expression for this kind of language:
$$b^*ab^*ab^*\dots ab^*$$
And i need to repeat it $2^n+273$ times. And altough $n\in\mathbb{N}$, The expression above gives me all the the words that are in language.
Or am i looking at this question the wrong way?
For any fixed value of $n$, the language $$ L_{n}=\{w:|w|_a=2^n+273\} $$ is certainly regular, and the regular expression you described will recognize it. But the question here is whether $$ L=\bigcup_{n\in\mathbb{N}}L_n = \{w:|w|_a=2^n+273 \text{ for some } n\in\mathbb{N}\} $$ is regular. It's not; and the easiest way to prove it is to use the so-called pumping lemma. The pumping lemma says that if $L$ is regular, then all sufficiently long strings in $L$ can be written as $xyz$, where $xy^i z$ is also in $L$ for all $i\ge 0$. In your case, consider the string $a^k \in L$, where $k=2^n+273$ for some large value of $n$. Assuming $L$ is regular, the pumping lemma says that there's some substring $y$ (necessarily $a^{|y|}$) such that $k+(i-1)|y|=2^n+(i-1)|y|+273$ is also of the form $2^{m(i)}+273$ for all $i$. That is, $$ 2^{m(i)}-2^n=(i-1)|y|, $$ or $$ 2^{m(i)}-2^{m(i-1)}=|y|. $$ But the distance between successive powers of $2$ keeps increasing, while the gap $y$ stays the same; so there can't be any such $|y|$, and $L$ can't be regular.