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.


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.