Processing math: 100%
Close
Close Window

OpenDSA Stand-alone Modules

Chapter 0 modules

Show Source |    | About   «  0.15. Regular Expressions   ::   Contents   ::   0.17. Closure Properties of Regular Grammars  »

Regular Grammars

1. Regular Grammars

Here is another way to describe a regular language.

Grammar G=(V,T,S,P)

represented byVvariables (nonterminals)A,B,..,ZTterminalsa,b,..,z,0,1,...9Sstart symbolPproductions (rules)

V, T, and P are finite sets.

Right-linear grammar:

all productions of formAxBAxwhere A,BV,xT

Note: x is a string of length 0 or more.

Left-linear grammar:

all productions of formABxAxwhere A,BV,xT

Definition:

A regular grammar is a right-linear or left-linear grammar.

Note

There is a more restrictive definition in which the length of x is 1. (Exercise in book.)

Example 1

G=({S},{a,b},S,P),P=SabSSλSSab

The language is (ab).

However, cannot mix left/right rules! So this is not a regular grammar.

Example 2

G=({S},{a,b},S,P),P=SaB|bS|λBaS|bB

This is a right linear grammar representing the language L={strings with an even number of a's},Σ={a,b}

1.1. Our Next Step

What we have already done:
Definition: DFA represents regular language
Theorem: NFA DFA
Theorem: RE NFA
What we will do next:
Theorem: DFA regular grammar

1.2. NFA from Regular Grammar

Theorem: L is a regular language if and only if regular grammar G such that L=L(G).

(Doing here for RR grammar, see book for proof sketch for LR grammar.)
() Given a regular grammar G, Construct NFA M such that L(G)=L(M)
Make a state for each non-terminal.
Make a transition on each terminal in that production rule.
Make it final if there is a production without non-terminals.
For rules with multiple terminals, need intermediate states.

Example 3

SaB|bS|λ
BaS|bB

This is a right linear grammar representing the language
L={ strings with an even number of a's },Σ={a,b}
strgtonfa

What about a rule like SabB? Make two states (S to intermediate state on a, then intermediate state to B on b).

Or Sab? Make two states (S to intermediate state on a, then intermediate state to an accepting state on B.

1 / 10 Settings
<<<>>>

Suppose we need to convert this Regular Grammar to an NFA

  1. S
  2. aB
  1. S
  2. aA
  1. A
  2. aA
  1. A
  2. bS
  1. A
  2. bB
  1. B
  2. bS
  1. B
  2. λ
Proficient Saving... Error Saving
Server Error
Resubmit

1.3. Right-linear Regular Grammar from DFA

Theorem: L is a regular language iff regular grammar G such that L=L(G).

() Given a DFA M, construct regular grammar G such that L(G)=L(M)

The process is pretty much the same as when we made an NFA from RRG:
Each DFA state gets a non-terminal.
Each transition gets a production rule.

Construct the Regular Grammar for the NFA

stnfatorg
G=({S,B},{a,b},S,P),
P=
Q0aQ1
Q1aQ0|bQ1|λ
1 / 6 Settings
<<<>>>

Suppose we need to convert this NFA to a Regular Grammar

Created with Raphaël 2.1.2
Q0
Q1
b
a
a
Proficient Saving... Error Saving
Server Error
Resubmit

1.4. Something to Think About

Example 4

L={anbnn>0}

Is language L regular? Can you draw a DFA, regular expression, or Regular grammar for this language?

Consider this grammar:

SaSbab

Nice and easy... but this grammar is not regular!

We will come back to this question later.

   «  0.15. Regular Expressions   ::   Contents   ::   0.17. Closure Properties of Regular Grammars  »

nsf
Close Window