Automata

{ "states": [ "Q1", "Q2", "Q3", "Q4", "Q5", "Halt" ], "finalStates": [ "Halt" ], "initialState": "Q1", "inputSymbols": [ "1", "*", "#", "-" ], "transitions": { "Q1": { "1": { "move": "R", "next": "Q2", "write": "1" } }, "Q2": { "1": { "move": "R", "next": "Q2", "write": "1" }, "*": { "move": "R", "next": "Q2", "write": "*" }, "-": { "move": "R", "next": "Q3", "write": "-" } }, "Q3": { "1": { "move": "L", "next": "Q4", "write": "*" }, "*": { "move": "R", "next": "Q3", "write": "*" }, "#": { "move": "R", "next": "Halt", "write": "#" } }, "Q4": { "*": { "move": "L", "next": "Q4", "write": "*" }, "-": { "move": "L", "next": "Q5", "write": "-" } }, "Q5": { "1": { "move": "R", "next": "Q2", "write": "*" }, "*": { "move": "L", "next": "Q5", "write": "*" } }, "Halt": {} }}

tm

Count Subtracter (unary subtracter)

A Turing Machine for subtraction of two unary numbers f(a-b) = c where a is always greater than b. E.g.: 11111-111 will give 11 on the tape.

Husain

Load in Editor

{ "states": [ "Q0", "Q1", "Q2", "Q4", "Q5", "Q3", "Q6", "Q7" ], "finalStates": [ "Q7" ], "initialState": "Q0", "inputSymbols": [ "a", "b", "#", "*" ], "transitions": { "Q0": { "a": { "move": "R", "next": "Q1", "write": "*" }, "b": { "move": "R", "next": "Q4", "write": "*" }, "#": { "move": "R", "next": "Q7", "write": "#" } }, "Q1": { "a": { "move": "R", "next": "Q1", "write": "a" }, "b": { "move": "R", "next": "Q1", "write": "b" }, "#": { "move": "L", "next": "Q2", "write": "#" } }, "Q2": { "a": { "move": "L", "next": "Q3", "write": "#" } }, "Q4": { "a": { "move": "R", "next": "Q4", "write": "a" }, "b": { "move": "R", "next": "Q4", "write": "b" }, "#": { "move": "L", "next": "Q5", "write": "#" } }, "Q5": { "b": { "move": "L", "next": "Q6", "write": "#" } }, "Q3": { "a": { "move": "L", "next": "Q3", "write": "a" }, "b": { "move": "L", "next": "Q3", "write": "b" }, "*": { "move": "R", "next": "Q0", "write": "*" } }, "Q6": { "b": { "move": "L", "next": "Q6", "write": "b" }, "a": { "move": "L", "next": "Q6", "write": "a" }, "*": { "move": "R", "next": "Q0", "write": "*" } }, "Q7": {} }}

tm

Even length palindrome

A TM machine for checking the palindrome of the string of even length, containing only 'a' and 'b'. For example: aabbaa, babaabab

Husain

Load in Editor

{ "states": [ "Q0", "Q1", "Q2", "Q3", "Q4", "Q5" ], "initialState": "Q0", "finalStates": [ "Q5" ], "inputSymbols": [ "0", "X", "c", "#" ], "transitions": { "Q0": { "0": { "move": "R", "next": "Q1", "write": "X" }, "c": { "move": "R", "next": "Q5", "write": "#" } }, "Q1": { "0": { "move": "R", "next": "Q1", "write": "0" }, "c": { "move": "R", "next": "Q2", "write": "c" } }, "Q2": { "0": { "move": "R", "next": "Q2", "write": "0" }, "#": { "move": "L", "next": "Q3", "write": "0" } }, "Q3": { "0": { "move": "L", "next": "Q3", "write": "0" }, "c": { "move": "L", "next": "Q4", "write": "c" } }, "Q4": { "0": { "move": "L", "next": "Q4", "write": "0" }, "X": { "move": "R", "next": "Q0", "write": "X" } }, "Q5": {} }}

tm

Count Adder

Add two numbers, represented by the count of zeros and separated by letter 'c'. For example, 2+3 will be 00c000 and result will be 5, that is, 00000.

Husain

Load in Editor

{ "states": [ "A", "B", "C", "D", "E" ], "finalStates": [ "E" ], "initialState": "A", "inputSymbols": [ "a", "X", "b", "#", "Y" ], "transitions": { "A": { "a": { "move": "R", "next": "B", "write": "X" }, "Y": { "move": "R", "next": "E", "write": "Y" } }, "B": { "b": { "move": "R", "next": "B", "write": "b" }, "a": { "move": "R", "next": "B", "write": "a" }, "#": { "move": "L", "next": "C", "write": "#" }, "Y": { "move": "L", "next": "C", "write": "Y" } }, "C": { "b": { "move": "L", "next": "D", "write": "Y" } }, "D": { "a": { "move": "L", "next": "D", "write": "a" }, "b": { "move": "L", "next": "D", "write": "b" }, "X": { "move": "R", "next": "A", "write": "X" } }, "E": {} }}

tm

a^n b^n Turing

Accepts strings with n number of 'a' followed by n number of 'b', using a turning machine.

Husain

Load in Editor

{ "states": [ "Q0", "Q1", "Q2", "Q3", "Q4" ], "initialState": "Q0", "finalStates": [ "Q1", "Q2" ], "inputSymbols": [ "a", "b" ], "transitions": { "Q0": { "a": "Q1", "b": "Q2" }, "Q1": { "a": "Q1", "b": "Q4" }, "Q2": { "b": "Q2", "a": "Q3" }, "Q3": { "a": "Q3", "b": "Q2" }, "Q4": { "b": "Q4", "a": "Q1" } }}

dfa

First and Last input same

DFA in which start and end symbol must be same Given: Input alphabet, Σ={a, b} Example strings: L = {ε, a, b, aa, bb, aba, bab, ababa, aabba, aaabbba,...}

Husain

Load in Editor

{ "states": [ "Q0", "Q1", "Q2", "Qf" ], "finalStates": [ "Qf" ], "initialState": "Q0", "inputSymbols": [ "a", "c", "b" ], "stackSymbols": [ "a", "#" ], "transitions": { "Q0": { "a": { "#": { "next": "Q1", "stack": "aa#" } } }, "Q1": { "a": { "a": { "next": "Q1", "stack": "aaa" } }, "c": { "a": { "next": "Q2", "stack": "a" } } }, "Q2": { "b": { "a": { "next": "Qf", "stack": null } } }, "Qf": { "b": { "a": { "next": "Qf", "stack": null } } } }}

pda

a^n c b^2n

Accepts strings over {a,b,c}, where, n number of 'a' is followed by one 'c' then 2n number of 'b'

Husain

Load in Editor

{ "states": [ "A", "B" ], "initialState": "A", "finalStates": [ "B" ], "inputSymbols": [ "a", "b" ], "stackSymbols": [ "#", "a" ], "transitions": { "A": { "a": { "#": { "next": "A", "stack": "a#" }, "a": { "next": "A", "stack": "aa" } }, "b": { "a": { "next": "B", "stack": null } } }, "B": { "b": { "a": { "next": "B", "stack": null } } } }}

pda

anbn

Accepts strings over {a,b}, with n number of 'a' followed by n number of 'b'

Husain

Load in Editor

{ "states": [ "q0", "q1", "q2", "q3" ], "initialState": "q0", "finalStates": [ "q0", "q1", "q2", "q3" ], "inputSymbols": [ "a", "b", "d", "c" ], "transitions": { "q0": { "a": "q0", "b": "q1", "d": "q2", "c": "q3" }, "q1": { "b": "q1", "d": "q2" }, "q2": { "d": "q2" }, "q3": { "c": "q3", "d": "q2" } }}

dfa

a(b + c)d

Accepts strings satisfying the regular expression: a*(b* + c*)d* Any number of a followed by any number of b OR any number of c then followed by any number of d

Husain

Load in Editor

{ "states": [ "Q0", "Q1", "Q2", "Q3", "Q4" ], "initialState": "Q0", "finalStates": [ "Q0" ], "inputSymbols": [ "1", "0" ], "transitions": { "Q0": { "0": "Q0", "1": "Q1" }, "Q1": { "0": "Q2", "1": "Q3" }, "Q2": { "0": "Q4", "1": "Q0" }, "Q3": { "0": "Q1", "1": "Q2" }, "Q4": { "0": "Q3", "1": "Q4" } }}

dfa

Divisible by 5

Accepts binary strings which are divisbile by 5

Husain

Load in Editor

{ "states": [ "Q0", "Q1", "Q2" ], "initialState": "Q0", "finalStates": [ "Q0" ], "inputSymbols": [ "0", "1" ], "transitions": { "Q0": { "0": "Q0", "1": "Q1" }, "Q1": { "0": "Q2", "1": "Q0" }, "Q2": { "0": "Q1", "1": "Q2" } }}

dfa

Divisible by 3

Accepts binary strings which are divisible by 3

Husain

Load in Editor

{ "states": [ "A", "B", "C", "D" ], "initialState": "A", "finalStates": [ "D" ], "inputSymbols": [ "a", "b", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "c" ], "transitions": { "A": { "a": "A", "b": "A", "d": "A", "e": "A", "f": "A", "g": "A", "h": "A", "i": "A", "j": "A", "k": "A", "l": "A", "m": "A", "n": "A", "o": "A", "p": "A", "q": "A", "r": "A", "s": "A", "t": "A", "u": "A", "v": "A", "w": "A", "x": "A", "y": "A", "z": "A", "c": "B" }, "B": { "a": "C", "b": "A", "c": "A", "d": "A", "e": "A", "f": "A", "g": "A", "h": "A", "i": "A", "j": "A", "k": "A", "l": "A", "m": "A", "n": "A", "o": "A", "p": "A", "q": "A", "r": "A", "s": "A", "t": "A", "u": "A", "v": "A", "w": "A", "x": "A", "y": "A", "z": "A" }, "C": { "t": "D", "a": "A", "b": "A", "c": "A", "d": "A", "e": "A", "f": "A", "g": "A", "h": "A", "i": "A", "j": "A", "k": "A", "l": "A", "m": "A", "n": "A", "o": "A", "p": "A", "q": "A", "r": "A", "s": "A", "u": "A", "v": "A", "w": "A", "x": "A", "y": "A", "z": "A" }, "D": { "a": "D", "b": "D", "c": "D", "d": "D", "e": "D", "f": "D", "g": "D", "h": "D", "i": "D", "j": "D", "k": "D", "l": "D", "m": "D", "n": "D", "o": "D", "p": "D", "q": "D", "r": "D", "s": "D", "t": "D", "u": "D", "v": "D", "w": "D", "x": "D", "y": "D", "z": "D" } }}

dfa

strings with 'cat'

Accepts lowercase strings those have atlease one occurance of 'cat'

Mohammad

Load in Editor

{ "states": [ "A", "B", "C" ], "initialState": "A", "finalStates": [ "C" ], "inputSymbols": [ "1", "0" ], "transitions": { "A": { "0": "B", "1": "A" }, "B": { "0": "C", "1": "A" }, "C": { "0": "C", "1": "A" } }}

dfa

Ending with 00

Accepts all strings over {0,1} which are ending with 00

Husain

Load in Editor

Community

Count Subtracter (unary subtracter)

Even length palindrome

Count Adder

a^n b^n Turing

First and Last input same

a^n c b^2n

anbn

a*(b* + c*)d*

Divisible by 5

Divisible by 3

strings with 'cat'

Ending with 00

a(b + c)d