Att beräkna antalet strängar av given längd som finns i ett språk är relaterat till klassiska problem med kombinatorik, formella språk och beräknings komplexitet. Här studerar vi problemets komplexitet när det gäller kontextfria språk. Det visas att för otvetydiga sammanhangsfria språk är en sådan beräkning "lätt" och kan utföras med effektiva parallella algoritmer. Tvärtom, för vissa sammanhangsfria språk av tvetydiga grad två blir problemet oinskränkt. Dessa resultat är relaterade till andra klassiska ämnen om att räkna problem, exponentiell tid igenkännliga språk och glesa uppsättningar.
Den beräkningsmässiga komplexiteten hos olika varianter av beräkning av antalet strängar av en viss längd i kontextfria språk undersöks av Bertoni et al. Hoppa över det.
The complexity of computing the number of strings of given length in context-free languages
{'venue': 'Theor. Comput. Sci.', 'journal': 'Theor. Comput. Sci.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}