0
$\begingroup$

I have the language $L = \{ 0^{2l} 1^m | l,m >= 0 \} \ where \ \Sigma= \{0,1\} $ which I am trying to find the class of language for, e.g. not context-free, context-free, regular.

By this notion I assume $L$ is context-free and has some pumping length $p$, and I will use the pumping lemma.

$w = 0^{2p}1^p$ and can be split into $w = uv^ixy^iz, i >= 0.$

$|w| > p$

I know that $vxy$ can only be in 3 places as it is of length at most $p$, these scenarios are:

-all 0's

-A mix of 0's and 1's.

-All 1's.

My thinking is that scenario 1 is invalid as it must always be an even length, and pumping up may break this. Scenarios 2 I am unsure although I think it follows the same logic as the first scenario, and scenario 3 could be pumped and still be in the language.

Does this mean $L$ is context-free? Can I also infer if $L$ is regular?

$\endgroup$
1
  • $\begingroup$ As a reminder: the pumping lemma for regular languages (resp. for context-free languages) can be used to prove that a language is not regular (resp. context-free). $\endgroup$
    – Nathaniel
    Oct 27, 2022 at 9:11

1 Answer 1

0
$\begingroup$

Your language is regular. A regular expression is e.g. $(00)^\ast1^\ast$. The numbers $l$ and $m$ are not in any relation to each other. You just have an even number of $0$s followed by an arbitrary number of $1$s.

$\endgroup$

Your Answer

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

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