Regular Grammar

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.

• Context:
  • It can be modeled by a Nondeterministic Finite State Machine.
  • Formally, (N, Σ, P, S) such that all the Production Rules in [math]\displaystyle{ P }[/math] are of one of the following forms:
    • A → a - where A is a Non-Terminal in N and a is a terminal in Σ.
    • A → aB - where A and B are in N and a is in Σ.
    • A → ε - where A is in N and ε denotes the Empty String, i.e. the string of length 0.
  • It can produce Regular Formal Languages.
  • …
• Counter-Example(s):
  • Context-Free Grammar.
• See: Chomsky Hierarchy.

---

---

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

• (Chomsky, 1957) ⇒ Noam Chomsky. (1957). “Syntactic Structures." Mouton de Gruyter.

---