Home

Welcome to the regular.language wiki!

Grammar

{
  "terminals" : ["a"],
  "nonTerminals" : ["S", "A"],
  "startSymbol" : "S",
  "rules" : ["S -> ", "S -> aA", "A -> a"]
}

Finite Automaton

{
  "states" : ["A", "B", "C"],
  "startState" : "A",
  "endStates" : ["C"],
  "alphabet" : ["a", "b", "c"],
  "transitions" : [
    "A -> B : b",
    "B -> C : c",
    "C -> C : c"]
}

isRegular(grammar) = true <=> for each rule in grammar isRegular(rule) = true, ∀ grammar ∈ Grammar
isRegular(rule) = true <=> 
[1] rule := <NonTerminal> -> <Terminal><NonTerminal>
[2] rule := <NonTerminal> -> <NonTerminal>
[3] rule := <NonTerminal> -> ∂ where <NonTerminal> := startSymbol

To Grammar
S -> aA <=> S -> A : a
s -> a <=> S -> W0 : a, where W0 is final state
S -> ∂ <=> S -> S : ∂, where S is final state 

To Automaton
S -> A : a <=> S -> aA
s -> W0 : a <=> S -> a, where W0 is final state
S -> S: ∂ <=> S -> ∂ where S is final state