Regular Grammar

From GM-RKB
Jump to navigation Jump to search

A Regular Grammar is a Grammar Class where the left-hand side is a Terminal Symbol and the right-hand side is either the Empty String, or a single terminal symbol, or a single terminal symbol followed by a nonterminal symbol.



References

2009

  • (Wikipedia, 2009) ⇒ http://en.wikipedia.org/wiki/Formal_grammar
    • In regular grammars, the left hand side is again only a single nonterminal symbol, but now the right-hand side is also restricted. The right side may be the empty string, or a single terminal symbol, or a single terminal symbol followed by a nonterminal symbol, but nothing else. (Sometimes a broader definition is used: one can allow longer strings of terminals or single nonterminals without anything else, making languages easier to denote while still defining the same class of languages.)


  • http://www.cse.unsw.edu.au/~billw/nlpdict.html#Chomskyhier
    • The Chomsky hierarchy is an ordering of types of grammar according to generality. The classification in fact only depends on the type of grammar rule or production used. The grammar types described in COMP9414 included:
      • unrestricted grammars (rules of the form a → b with no restrictions on the strings a and b)
      • context sensitive grammars (rules of the form a → b with the restriction length(a) <= length(b))
      • context free grammars (rules of the form X → b where X is a single non-terminal symbol)
      • regular grammars (rules of the form X → a and X → aN where X and N are non-terminal symbols, and a is a terminal symbol.)

1957