1
$\begingroup$

I would like to know if there is a name for CFG grammars (or grammars in general) in which there is a fixed number of "distingushed" terminals or in which there is a terminal that appears a fixed number of times (in the generated strings).

For example:

$L(G) = \{ 0^a 1 0^b 1 0^c \mid a = b \text{ or } a = c \}$

In this case the symbol $1$ appears exactly two times in every string and "acts as a separator".

Clearly, in this family of languages, the distinguished terminal(s) forces the pumpable substrings $v$, $x$ (in $uv^nwx^ny)$) to belong to at most two distinct "segments" and forbid each one of them to cover more than one segment.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.