Interchange lemma
id:
interchange-lemma-314-1735199
title:
Interchange lemma
text:
In the theory of formal languages, the interchange lemma states a necessary condition for a language to be context-free, just like the pumping lemma for context-free languages. It states that for every context-free language L there is a c > 0 such that for all n ≥ m ≥ 2 for any collection of length n words R ⊂ L there is a Z = { z 1 , … , z k } ⊂ R with k ≥ | R | / , and decompositions z i = w i x i y i such that each of | w i | , | x i | , | y i | is independent of i , moreover, m / 2 < | x i |
brand slug:
wiki
category slug:
encyclopedia
description:
original url:
https://en.wikipedia.org/wiki/Interchange_lemma
date created:
date modified:
2022-09-18T16:32:06Z
main entity:
{"identifier":"Q60789213","url":"https://www.wikidata.org/entity/Q60789213"}
image:
fields total:
13
integrity:
13