Enumeration of words in context-free languages using Haskell

• Autorzy: Wieczorek W.

Identyfikatory

DOI

10.21936/si2017_v38.n1B.790

Warianty tytułu

PL

Haskellowa implementacja wyliczania słów języków bezkontekstowych

• Języki publikacji: EN

Abstrakty

EN

The cross-section enumeration problem is to list all words of length n in a language L in lexicographic order. We present the Haskell implementation of an algorithm for the cross-section enumeration problem for any language defined by a context-free grammar without unit productions and without λ-productions.

PL

Jednym z rozważanych problemów kombinatorycznych jest wyliczenie w porządku leksykograficznym wszystkich słów o długości n należących do pewnego języka L. W niniejszym artykule zaprezentowano algorytm – wraz ze stosownym kodem w języku Haskell – służący do takiego wyliczania. Zakładamy, że język L zdefiniowany jest za pomocą gramatyki bezkontekstowej bez produkcji jednostkowych i bez λ-produkcji.

Słowa kluczowe

EN

context-free language; enumeration; Haskell; lexicographic order

PL

język bezkontekstowy; enumeracja; Haskell; kolejność alfabetyczna

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Studia Informatica
• Rocznik: 2017
• Tom: Vol. 38, nr 1B
• Strony: 5--17
• Opis fizyczny: Bibliogr. 13 poz.

Twórcy

autor

Wieczorek W.

• Silesian University, Institute of Computer Science, ul. Będzińska 39, 41-200 Sosnowiec, Poland

Bibliografia

• 1. Ackerman M., Shallit J.: Efficient enumeration of words in regular languages. Theoretical Computer Science, vol. 410, 2009, p. 3461÷3470.
• 2. Adams S.: Efficient sets: a balancing act. Journal of Functional Programming, vol. 3, 11993, p. 553÷562.
• 3. Andrews G.E.: The Theory of Partitions. Encyclopaedia of Mathematics and Its Applications 2, Addison-Wesley (1976), reissued CUP 1998.
• 4. Asveld P.: Generating all permutations by context-free grammars in Chomsky normal form. Theoretical Computer Science, vol. 125, 2006, p. 315÷328.
• 5. Bertoni A., Goldwurm M., Santini M.: Random generation for finitely ambiguous context-free languages. Theoretical Informatics and Applications, vol. 35, 2001, p. 499÷512.
• 6. Goldwurm M.: Random generation of words in an algebraic language in linear binary space. Information Processing Letters, vol. 54, 1995, p. 229÷233.
• 7. Haskell libraries. URL http://www.haskell.org/ghc/docs/latest/html/libraries
• 8. Hopcroft J.E., Ullman J.D.: Introduction to automata theory, languages and computation. Addison-Wesley, 1979.
• 9. Hutton G.: Programming in Haskell. Cambridge University Press, 2007.
• 10. Mäkinen E.: On lexicographic enumeration of regular and context-free languages. Acta Cybernetica, vol. 13, 1997, p. 55÷61.
• 11. Mandoiu I.I., Zelikovsky A.Z. (Eds.): Bioinformatics Algorithms: Techniques and Applications. John Wiley & Sons, 2008.
• 12. Papadimitriou C.H., Steiglitz K.: Combinatorial Optimization: Algorithms and Complexity. Dover Publications, 1998.
• 13. Rabhi F., Lapalme G.: Algorithms: A Functional Programming Approach. AddisonWesley, 1999.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017)