Nagy, BenedekAngyal, Dávid2014-05-052014-05-052014-05-052014-05-05http://hdl.handle.net/2437/191126In this thesis we investigate some interesting properties of the family of permutation languages and its subclasses. Permutation grammars are context-free grammars extended with special non-context-free rules: permutation rules. Permutation rules have a sequence of nonterminal symbols on the left-hand side and a permutation of that sequence on the right-hand side. The simplest permutation rules are of the form AB -> BA, more complex permutation rules can be obtained by length increase, for instance ABC -> CAB. We discuss some of the subclasses of permutation grammars. We also introduce a modification to Earley's parser algorithm for context-free grammars in order to handle Perm(2, 1) grammars and discuss an efficient implementation.41enformal languagespermutation languagesparsingDEENK Témalista::Informatika::Számítógéptudomány