Quartz 5

Regular Formal Language

1 min read

A regular formal language or a Type 3 language is produced by rules and where are variables and is a termination symbol.

Proposition

If are regular grammars and , then

  1. If RCG, then
  2. If RUG, then

Theorem

TFAE:

  1. is regular
  2. for Deterministic Automata
  3. for Nondeterministic Automata

Lemma

Regular Pumping Lemma

Graph View

Backlinks