automata-golf

KO | EN

gitlite — search

#javascript #python #hacktoberfest #react #ai #typescript #llm #go #golang #android #machine-learning #rust #deep-learning #linux

★ 20 Open GitHub ↗

A domain-specific language (DSL) for parsing regular, context-free and recursively enumerable languages.

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# automata-golf

A domain-specific language (DSL) for parsing regular, context-free and recursively enumerable languages.

In `automata-golf`, a machine is defined by a series of path statements.
There's no need to explicitly define states or transitions.

The example below shows a machine with an initial state `s0`, which transitions
via `f` to and from the accepted state `s1` .

```
# 1,2, and 3 are all equivalent:

# 1
.s0 -f> (s1) -f> s0;

# 2
.s0 <f> (s1);

# 3
s1 -f> .s0;
s0 <f- (s1);
```

Starting states are prefixed with `.`; Success states are wrapped in `(` `)`.

## Pattern matching

Regex is supported for pattern matching

```
/^s[0-9]/ -g> t1;
```

## Stacking transitions

Multiple transitions from the same state can be stacked up:

```
.s0 -f> -g> -h> s1;
```

## Pushdown automata

`automata-golf` supports pushdown automota, i.e. a finite-state machine with
a stack and transitions that push/pop the stack.

The following transitions to `s1` on input `f` when `a` is top of the stack.
Upon the transition, it pushes `b` to the stack.

```
.s0 -f[a:b]> s1;
```

### Multiple stacks

2-stack PDAs are supported, making them equivalent to Turing machines. See the
example and corresponding automaton diagram below.

```
.s0 -f[a:b, _:c]> s1;
```

### Epsilon transitions

Epsilon is represented by `_`. For example the following transitions to `s1`
and pushes `$` to the second stack without consuming any input or popping either stack.

```
.s0 -_[_:_, _:$]> (s1);

# or equivalently:

.s0 -[_, :$]> (s1);
```

# Examples

## Regular languages

Regular languages can be captured using finite-state machines.

### Odd binary numbers

The following program accepts all binary numbers ending in `1`

```js
const { build } = require("./automata-golf/index.js");

const { machine } = build(`
.s0 -0> -1> s0 -1> (s1);
`);

machine.consume("10110").inAcceptState(); // false
machine.consume("1011").inAcceptState(); // true
```

### Self-driving robot

The following finite-state machine creates a robot that can be turned on and off,
and switches direction when it collides.

```js
const { build } = require("./automata-golf/index.js");

const { machine } = build(`
.off <push> forward <collide> backward -push> off;
`);

machine.consume(["push", "collide"]).state; // backward
```

## Context-free languages

Pushdown automota are required to parse context-free languages.

### Odd-length palindromes

The following accepts all odd-length palindromes in the language `{a, b}`

```js
const { build } = require("automata-golf/index.js");

const { machine } = build(`
.s0 -[:$]> s1;
s1 -a[:a]> -b[:b]> s1;
s1 -a> -b> s2;
s2 -a[a]> -b[b]> s2;
s2 -[$]> (s3); 
`);

machine.consume("abbba").inAcceptState(); // true
machine.consume("abb").inAcceptState(); // false
```

Note the program can be condensed to

```
.s0 -[:$]> s1 -a[_:a]> -b[:b]> s1 -a> -b> s2 -a[a]> -b[b]> s2 -[$]> (s3);
```

## Recursively enumerable languages

Recursively enumerable languages can be parsed by using a pushdown automaton with 2 stacks, equivalent to a Turing machine.

### anbncn

The following accepts input of the format anbncn:

```js
const { build } = require("automata-golf/index.js");

const machine = build(`
.s0 -a[:a]> s0 -_> s1 -b[a, :b]> s1 -_> s2 -c[_, b]> (s2);
`);

machine.consume("aabbcc").inAcceptState(); // true
machine.consume("abbc").inAcceptState(); // false
```

## Build to JS

The machine can be written to a JS file

```js
// A.js
const { build } = require("automata-golf/index.js");
build(".s0 -f> (s1)", { emitFile: "./machine.js" });

// B.js
const machine = require("./machine.js");
machine.consume("f");
```

### Target

Set `target` to `'browser'` to generate a machine that can be run in a browser
environment:

```js
build(".s0 -f> (s1)", { emitFile: "./machine.js", target: "browser" });
```

automata-golf

오늘의 추천 프로젝트

Was this content helpful?

Recent Feedback

automata-golf

오늘의 추천 프로젝트

Was this content helpful?

Recent Feedback

Download README