Sowohl für die Klasse der kontextfreien, wie auch für die der regulären ''Grammatiken'' gilt ein Schleifensatz (oder: Pumping-Lemma, Lemma von Bar-Hillel), dessen Aussage es oft erlaubt, den Beweis der Nichtzugehörigkeit einer bestimmten Sprache zur entsprechenden Sprachklasse unschwer durch Widerspruch zu führen.
''[[formale Sprache]]n'': Ein [[Semi-Thue-System]] aus Ersetzungsregeln in einem Syntaxbaum, das genau die Sätze einer bestimmten formalen Sprache zu generieren fähig ist