Loading [MathJax]/jax/output/HTML-CSS/jax.js

CS4114 Coursenotes

Chapter 2 Week 3

Show Source | | About « 2.1. Regular Languages and Expressions :: Contents :: 2.3. Closure Properties of Regular Languages »

2.2. Regular Grammars¶

2.2.1. Regular Grammars¶

Here is another way to describe a language: Use a grammar.

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

$V$ : Variables (nonterminals), represented by $A, B, ..., Z$

$T$ : Terminals, reprsented by $a, b, ..., z, 0, 1, ..., 9$

$S$ : Start symbol

$P$ : Productions (rules)}

$V$ , $T$ , and $P$ are finite sets.

2.2.2. Right-linear grammar¶

All productions are of the form:

$A \rightarrow xB$

$A \rightarrow x$

where $A, B \in V, x \in T^*$

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

2.2.3. Left-linear grammar¶

all productions of form

$A \rightarrow Bx$

$A \rightarrow x$

where $A, B \in V, x \in T^*$

Definition:

Any right-linear or left-linear grammar is defined to be a regular grammar.

(There is a more restrictive definition in which the length of $x$ is $\leq 1$ .)

2.2.4. Example 1¶

$G = (\{S\},\{a,b\},S,P),$

$P =$

$S \rightarrow abS$

$S \rightarrow \lambda$

$S \rightarrow Sab$

<< What language is this? >>

2.2.5. Example 1¶

$G = (\{S\},\{a,b\},S,P),$

$P =$

$S \rightarrow abS$

$S \rightarrow \lambda$

$S \rightarrow Sab$

Cannot mix left/right rules! This is not a regular grammar.

2.2.6. Example 2¶

$G = (\{S\},\{a,b\},S,P),$

$P =$

$S \rightarrow aB \mid bS \mid \lambda$

$B \rightarrow aS \mid bB$

<< What language is this? >>

2.2.7. Example 2¶

$G = (\{S\},\{a,b\},S,P),$

$P =$

$S \rightarrow aB \mid bS \mid \lambda$

$B \rightarrow aS \mid bB$

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

2.2.8. Our Next Step¶

Done before:

Definition: DFA represents regular language

Theorem: RE $\Longleftrightarrow$ DFA

Next:

Theorem: DFA $\Longleftrightarrow$ regular grammar

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

2.2.9. Proof: NFA from Regular Grammar¶

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

( $\Longleftarrow$ ) 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.

<< What is the machine for Example 2? >>

2.2.10. RRG to NFA Example¶

<<See 4.3.2>>

2.2.11. Proof: RR Grammar from DFA¶

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

( $\Longrightarrow$ ) 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.

2.2.12. NFA to RRG Example¶

<<See 4.3.3>>

2.2.13. Something to Think About¶

$L = \{a^nb^n \mid n>0\}$

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

Contact Us || Privacy | | License « 2.1. Regular Languages and Expressions :: Contents :: 2.3. Closure Properties of Regular Languages »