0
$\begingroup$

For any alphabet and any natural number k, a language of strings at least k is decidable.

So my question is having some alphabet (let's say (0,1)) and some number let's say k=5 then my language has every string of 1's and 0's that are 5 or more characters at length (ie 01101, 011011 belong to language, while 011,10,1100 does not). Can such language be decidable and how so?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

The easy and immediate way to see this is to note that the language of strings of length at most $k$ is finite, therefore it is regular. Regular languages are closed under complementation (just switch the accept and reject states), so your language of strings of length greater than $k$ is also regular.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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