One of the ChomskyHierarchy in TransformationalGrammar.
ComputerScience에서 RegularExpression과 동등함
RegularGrammar 에서의 모든 production rule 은 다음과 같은 form 이다.
- or : nonterminal : terminal
※ FiniteStateAutomata RegularGrammar 에 상응하는 Parsing automaton 은 FiniteStateAutomata 이다.
※ Moore vs. Mealy machines Transition을 accept 하는 finite automata 는 Mealy machine 이라 불리워진다. State를 accpet 하는 finite automata는 Moore machine 이라 불리워진다. 이 두가지 종류의 machine 은 interconvertible 하다.
※ Deterministic vs. nondeterministic automata Deterministic finite automaton 에서는 한 개 이상의 accepting transition 은 불가능하다. 어떠한 nondeterministic finite automaton 도 deterministic finite automaton 으로 변환될 수 있다는 것이 증명되었다.
※ PROSITE patterns PROSITE pattern 의 syntax 는 standard RegularExpression syntax 와 가깝다.
※ What a regular grammar can't do Regular grammar 가 기술할 수 없는 language L 의 두가지 고전적인 예 1. L 이 형태의 string을 포함할 때 (palindrome language) 2. L 이 형태의 string을 포함할 때 (copy language)
확률을 고려한다면 그것은 StochasticRegularGrammar