There are 256 formal languages $L$ with $L \subseteq \{w \in \{a,b\}^* \ \vert \ \ \vert w \vert = 3 \}$



My question is why there are 256 formal languages. If I calculate the possible combinations with length 3 I get 6 combinations:

$M =\{aaa, aab, abb, bbb, bba, baa\}$

Calculalting the power set results in: $2^M = 2^6 = 64$

Where did I go wrong the get $64$ as result?


1 Answer 1


That would be eight combinations, as $2^3=8$. You missed $aba$, and another one.

  • $\begingroup$ Oh I see... I should go to bed now .. :) Thanks! $\endgroup$
    – Bobface
    Commented Mar 3, 2017 at 23:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.