Skip to content

Latest commit

 

History

History
232 lines (177 loc) · 14.9 KB

README.md

File metadata and controls

232 lines (177 loc) · 14.9 KB
Raw

LangToGroup

Build Status DOI

This project provides an opportunity to build a grammar group representation in two ways, which is displayed in the following picture:

First approach

Implementation of Isoperimetric and Isodiametric Functions of Groups in Haskell.

Implementation algorithm building the presentation of the group for a formal language with the preservation of the language. The implementation of this algorithm is necessary for research in the field of formal languages with the involvement of the group-theoretical methods. At present, there are only theoretical works showing the possibility of such construction, however, the algorithm and its implementation are absent up to this point. As far as we know, this implementation is the first in its area.

Second approach

Implementation of building Turing machine by boolean grammar algorithm, described in Boolean grammars and algorithm, descrbied in An Introduction to the Theory of Groups, which by given Turing machine builds group presentation via building semigroup presentation.

Modifications of second approach

There are two modifications of second approach, which produce a more compact group presentation, but this modifications haven't strict theoretical proof of saving properties of original approach. So, use them if size of group presentation is more important than theoretical properties.

This modifications of second approach use modified conversions from Turing machine to semigroup representation (here G is set of generators and R is set of relations of produced semigroup presentation):

Original conversion (in second approach)

This conversion is represented in An Introduction to the Theory of Groups

First modified conversion (in second_a approach)

This conversion uses the same set of generators as the original, but smaller size of set of relations

Second modified conversion (in second_b approach)

This conversion uses different set of generators as opposed to the first conversion

Building

stack build

Testing

stack test

Usage

stack run -- LangToGroup-cli <options>

Options

  • -i file_path --input=file_path
    Full path to file with grammar definition
  • -o file_path --output=file_path
    Full path to file for printing results
  • -e file_path --error=file_path
    Full path to file, where errors should be recorded during parsing
  • -a approach --approach=approach
    Used approach (see section Approaches)
  • -I objects --info=objects
    Print useful information about objects (see section Objects)
  • -h --help
    Print help and exit

Approaches

Objects

  • grammar
    Input grammar (context-free, conjunctive or boolean)
  • turing_machine, tm
    Produced Turing machine (its type depends on used approach)
  • group_presentation, gp
    Produced group presentation

NOTE: When enumerating objects, they must be separated by commas WITHOUT SPACES!

Examples

  • stack run -- LangToGroup-cli -i grammar.txt -a second_b -I tm,gp

    If you want build presentation of grammar via second modification of the second approach and get metrics of produced group presentation and Turing machine

  • stack run -- LangToGroup-cli -i grammar.txt -o group_presentation.txt -a first

    If you want to build presentation of grammar via first approach and save produced group presentation to file

Examples of input grammar

Here are some format restrictions which grammars should satisfy to be handled by group presentation builder properly:

  • Empty word specified via Eps;
  • Conjunction and negation logical signs for defining boolean and conjunctive grammars should be written as & and ! respectively;
  • All nonterminals must have one capital letter and zero or more small letters in their names;
  • All terminals must have one or more small letters in their names;
  • First string must contain start nonterminal, set of nonterminals, set of terminals, separated by ; sign;
  • In subsequent lines grammar rules should be specified;
  • All signs, used for defining grammar as ;, ->, &, !, should be written exactly after previous signs and grammar symbols without commas, and there is a space after last sign;
  • Here are examples of input grammars, satisfying restrictions above:

Boolean grammar

S; S Sa; c v b 
S-> c&! v&! Sa&! Eps
Sa->! b
S-> a& b&! v&! Sa&! Eps

Conjunctive grammar

S; S Abc D Cr; c b d e
S-> D c& d Abc
Abc-> b
D-> Cr
Cr-> e

Context-free grammar

S; S A D1; c2 b e
S-> c2 D1 A
A-> b
D1-> e
  • Also there are files with experiment grammars in folder \examples\grammar\experiments with correct input.

NOTE: second approach for building group presentation accepts only grammar in normal form due to the specifics of the algorithm described in the article on the construction of a Turing machine by a boolean grammar!

Experiments

Here are the tables with some examples of building group presentations by different grammars, where:

  • States -- number of states in built Turing machine,
  • Gen -- number of generators,
  • Rel -- number of relations,
  • N -- number of rules in normal grammar.

Running experiments for the first approach

Language Grammar N States Generators Relations
1 rule CFG 1 6 89508 56187
Dyck language without empty word CFG 10 77 2798322 1773449
CFG 2 10 228160 129611
CFG 5 63 2241518 1355357

Running experiments for the second approach

Language Grammar N States Generators Relations
1 rule CFG 1 120 2300 28171
Dyck language without empty word CFG 10 943 40414 1025570
CFG 2 221 7384 149982
CFG 5 719 29510 719150
Conjunctive 14 3459 179112 5619872
Boolean 14 2498 125587 3691770
Boolean 14 3461 185307 5999829

Running experiments for the second approach, modification a

Language Grammar N States Generators Relations
1 rule CFG 1 120 1564 18603
Dyck language without empty word CFG 10 943 19221 474552
CFG 2 221 4193 82971
CFG 5 719 14350 340150
Conjunctive 14 3459 79023 2417024
Boolean 14 2498 58360 1674960
Boolean 14 3461 81376 2570106

Running experiments for the second approach, modification b

Language Grammar N States Generators Relations
1 rule CFG 1 120 881 8164
Dyck language without empty word CFG 10 943 7506 145444
CFG 2 221 1683 25620
CFG 5 719 5701 105950
Conjunctive 14 3459 27624 661568
Boolean 14 2498 20200 455220
Boolean 14 3461 27655 683100

Execution (old version)

NOTE: Old CLI was saved because some of posibilities aren't available in new CLI.

For run experiments and print its numerical results you can use is_det <bool> flag.

So, for print experiments' results using deterministic symmetrization:

stack exec -- LangToGroup-printer --is_det true

using nondeterministic symmetrization:

stack exec -- LangToGroup-printer --is_det false

Printing example transformations in LaTeX

Grammar's transformations also can be printed in LaTeX. For this should be used --print_example <grammar> flag. The following grammars can be used as print examples: "one" --- one rule grammar, "a*" --- grammar for regular language , "dyck" --- Dyck language grammar.

For example,

stack exec -- LangToGroup-printer --is_det true --print_example one

Output filename can be specified by -o <filename> flag.

Printing example group presentation in Gap-format file

For this you can use -G flag without a parameter, but with --is_det <bool> and --print_example <grammar> flags. Also, output filename can be specified by -o <filename> flag, if it does not speccified it been printing with default filename "out.txt".

For example, following prints in "out.txt" a group presentation, which obtained from Dyck language grammar using nondeterministic symmetrization:

stack exec -- LangToGroup-printer -G --is_det false --print_example dyck