0
$\begingroup$

I've been solving a lot of questions lately about determining the type of a given language, by type I mean whether it's regular, CFL, in P, Turing-decidable, Turing-acceptable, or all the languages. and I have this language here: $$L=\{w:|w|\text{ is even, and it has }\frac{|w|}2\text{ consecutive 0's}\}$$ So my main purpose is not actually to know the type of this language but I've faced a lot of questions that asked in the same manner, meaning it asks if the given language has a substring with some characteristics in the first half of a string $w$ in the language or such a thing as appears above.

So I'm searching for an approach that I can adopt to solve such questions.

Also, I would like an answer for the type of the above language.

I assume the language to be CFL but don't really know how to build finite automaton or CFG to decide it, it's clear that it's in P but I'm willing to know if it's CFL or regular.

$\endgroup$

1 Answer 1

1
$\begingroup$

The $|w|$ is even requirement can be checked by a finite state automaton, so that is not a real restriction. Comparing two numbers (the total length $|w|$ and the length of a consecutive sequence of $0$'s) is usually impossible for FSA.

Now to determine the type, following this intuition, you will have to show the language is CFL by building a suitable grammar, and showing it is not in REG, probably by applying the pumping lemma for regular languages.

To build a CFG first try to build one for $\{ 1^i 0^j 1^k \mid j=i+k\}$, and then change it in such a way that any number of $1$ can be changed into additional $0$.

$\endgroup$
2
  • $\begingroup$ Well, I succeeded to build a grammar for the language you've given but I don't really find it helpful to the language I asked for, it looks similar and I think it has a relation to it but I don't really recognize this relation and therefore I can't build a grammar for it, so if you have one please provide me with it. $\endgroup$
    – Mohamad S.
    Jun 5, 2022 at 19:20
  • 2
    $\begingroup$ @MohamadS.: In a sentence in that language, how many 0's are there, as a function of the total length of the sentence? Bonus question: is it possible for the total length 9f the sentence to be odd? $\endgroup$
    – rici
    Jun 5, 2022 at 21:12

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.