CS 422 — Automata Theory Fall 2009
CS106 — Compiler Principles and Construction
Fall 2011
Lecture 1: Grammar, Automata, DFA
MUST FIT
Dr. Liang
Grammar, Automat, DFA, Dr. Zhiyao Liang
1
Grammars — Definition
A grammar G is defined as a quadruple:
G = (V, T, S, P)
V is a finite set of objects called variables
T is a finite set of objects called terminal symbols
S V is a special symbol called the Start symbol
P is a finite set of productions or “production rules”
Sets V and T are nonempty and disjoint
Grammar, Automat, DFA, Dr. Zhiyao Liang
2
Grammars – rules and derivation
Production rules have the form:
x y
where x is an element of (V T)+ and y is in (V T)*
Given a string of the form
w = uxv
and a production rule
x y
we can apply the rule, replacing x with y, giving
z = uyv
We can then say that
w z
Read as “w derives z”, or “z is derived from w”
Grammar, Automat, DFA, Dr. Zhiyao Liang
3
Grammars — derivation
If w1 w2 w3 … wn,
then we say that w1 derives wn , and write
*
w1 wn
The * indicates that an unspecified number of steps can be taken to derive wn from w1.
Note that *
w w
Grammar, Automat, DFA, Dr. Zhiyao Liang
4
Grammars — the language
Let G = (V, T, S, P)
The set
*
L(G) = {w T* : S w}
is the language generated by G.
If w L(G), then the sequence
S w1 w2 … wn w
Is a derivation of the sentence w.
The strings in this derivation, S, w1 , … wn y contain variables as well as terminals, and are called the sentential forms of the derivation.
Grammar, Automat, DFA, Dr. Zhiyao Liang
5
Grammars — example
Consider the grammar G = (V, T, S, P), where:
V = {S}
T = {a, b}
S = S,
P = S aSb
S
Grammar, Automat, DFA, Dr. Zhiyao Liang
6
Grammars – example cont.
What are some of the strings in this language?
S aSb ab
S aSb aaSbb aabb
S aSb aaSbb aaaSbbb aaabbb
It is obvious the language generated by this grammar is:
L(G) = {anbn : n 0}
Proof: All sentential forms must the form wi = aiSbi , and then finally to get a sentence, we must apply the production rule S .
Grammar, Automat, DFA, Dr. Zhiyao Liang
7
Designing a grammar
Find a grammar that generates:
L = {anbn+1 : n 0}
So the strings of this language will be:
b (0 a’s and 1 b, when n = 0)
abb (n = 1)
aabbb (n = 2) . . .
One attempt: S Saab
This grammar can generate nothing
How about S Saab ; S
This grammar can only generate
aab, aabaab, aabaabaab, …
Grammar, Automat, DFA, Dr. Zhiyao Liang
8
Designning a grammar
What is the grammar (rules) for L’ = {anbn : n 0}
S aSb
S
The rule S rule is needed
Then the rules for L = {anbn+1 : n 0} are
S Ab
A aAb
A
How about
S Sb
S aSb
S ?
Grammar, Automat, DFA, Dr. Zhiyao Liang
9
Try Some Exercises
Give a simple description of the language generated by the grammar with productions
S aA
A bS
S
What language does the grammar with these productions generate?
S Aa
A B
A Aa
Grammar, Automat, DFA, Dr. Zhiyao Liang
10
Automata
A model of an abstract computing device:
Input File
Control Unit (with finite states)
Computation Result
Deterministic Finite Autoata
Pushdown Automata (with a stack)
Turing Machine (with a tape)
Grammar, Automat, DFA, Dr. Zhiyao Liang
11
A picture of an abstract automata
Grammar, Automat, DFA, Dr. Zhiyao Liang
12
Three Basic Concepts – The Big Picture
Languages
A set of strings based on a certain alphabet
Grammars (generates languages)
Automata (recognize, decide languages)
The big picture
What can be computed?
Languages that can be generated or recognized?
What cannot be computed.
The paradoxes
The incompleteness theorem
The undecidability
Grammar, Automat, DFA, Dr. Zhiyao Liang
13
1st model — Deterministic Finite Automaton (DFA)
Finite Control
Read only Head
Grammar, Automat, DFA, Dr. Zhiyao Liang
14
DFA (contd.)
The DFA has:
a finite set of states
1 special state – initial state
0 or more special states – final states
input alphabet
transition table containing
(state, symbol) -> next state
Grammar, Automat, DFA, Dr. Zhiyao Liang
15
Informally — How does a DFA work?
An input string is placed on the tape (left-justified).
DFA begins in the start state.
Head placed on leftmost cell.
DFA goes into a loop until the entire string is read.
In each step, DFA consults a transition table and changes state based on (s, ) where
s – current state
– symbol scanned by head
Grammar, Automat, DFA, Dr. Zhiyao Liang
16
How does a DFA work? (contd.)
After reading input string,
if DFA state final, input accepted
if DFA state not final, input rejected
Language of DFA — set of all strings accepted by DFA.
Grammar, Automat, DFA, Dr. Zhiyao Liang
17
Pictorial representation of DFA
(q,σ) -> q’
Grammar, Automat, DFA, Dr. Zhiyao Liang
18
Example: Diagram of DFA
L = {a2n + 1 | n >= 0}
Answer:
L = {a, aaa, aaaaa, …}
Grammar, Automat, DFA, Dr. Zhiyao Liang
19
JFLAP Step-By-Step
aaa
Grammar, Automat, DFA, Dr. Zhiyao Liang
20
JFLAP Step-By-Step
aaa
Grammar, Automat, DFA, Dr. Zhiyao Liang
21
JFLAP Step-By-Step
aaa
Grammar, Automat, DFA, Dr. Zhiyao Liang
22
JFLAP Step-By-Step
aaa
Grammar, Automat, DFA, Dr. Zhiyao Liang
23
Formal definition of DFA
DFA M = (Q, , , s, F)
Where,
Q is finite set of states
is input alphabet
s Q is initial state
F Q is set of final states
: Q X -> Q
Grammar, Automat, DFA, Dr. Zhiyao Liang
24
Formal definition of L(M)
L(M) – Language accepted by M
Define * (extends to strings):
*(q, ) = q
*(q, wσ) = (*(q,w),σ), w – string σ – symbol
Definition: L(M) = { w in * | *(s,w) is in F }.
Grammar, Automat, DFA, Dr. Zhiyao Liang
25
Example: L(M) = {w in {a,b}* | w contains even no. of a’s}
Grammar, Automat, DFA, Dr. Zhiyao Liang
26
JFLAP Step-By-Step
aa
Grammar, Automat, DFA, Dr. Zhiyao Liang
27
JFLAP Step-By-Step
aa
Grammar, Automat, DFA, Dr. Zhiyao Liang
28
JFLAP Step-By-Step
aa
Grammar, Automat, DFA, Dr. Zhiyao Liang
29
JFLAP Step-By-Step
ab
Grammar, Automat, DFA, Dr. Zhiyao Liang
30
JFLAP Step-By-Step
ab
Grammar, Automat, DFA, Dr. Zhiyao Liang
31
JFLAP Step-By-Step
ab
Grammar, Automat, DFA, Dr. Zhiyao Liang
32
Given a language, how to define DFA?
Creative process requiring you to:
(i) Put yourself in DFA’s shoes
(ii) Find finite amount of info, based on
which string accepted/rejected
(iii) From step (ii), determine number of states and then transitions.
Grammar, Automat, DFA, Dr. Zhiyao Liang
33
Regular Languages
Definition: A Language is regular iff there is a DFA that accepts it.
Examples:
{}
*
{w in {0,1}* | second symbol of w is a 1} Exercise
{w in {0,1}* | second last symbol of w is a 1} Exercise
{w in {0,1}* | w contains 0100 as a substring} – (importance?)
When one 0 is read, it could be the start of 0100, or the third character of 0100.
Grammar, Automat, DFA, Dr. Zhiyao Liang
34
Acknowledgement
Some slides are chosen from or based on Professor Rakesh Verma’s lecture notes of the course “Introduction to Theory of Computation” in University of Houston, Texas, USA.
Grammar, Automat, DFA, Dr. Zhiyao Liang
35
Exercises
(for discussion in class, with bonus credits)
2.1 Find the grammar for S = {a}
L = { w: |w mod 3 > 0}
2.2 Are the two grammars with respective productions
S aSb |ab |
and
S aAb |ab
A aAb|
equivalent?
2.3 Find a grammar that generates the language
L = {w wR | w in {a, b}+ }
2.4 Design DFAs for the following languages
{w in {0,1}* | second symbol of w is a 1}
{w in {0,1}* | second last symbol of w is a 1}
{w in {0,1}* | w contains 0100 as a substring}
Grammar, Automat, DFA, Dr. Zhiyao Liang
36
/docProps/thumbnail.jpeg