FIT2014 Lecture Notes - Lecture 11: Context-Free Grammar, Pushdown Automaton, Regular Grammar
28 Jun 2018
School
Department
Course
Professor
Lecture 11 Regular Grammars and pushdown Automata
NFA to CFG
1. Name all states in NFA by a symbol
a. Call the start State S
2. For each edges
3. For each edge
Write X Y
4. write X aX
5. Fo each final state X write X ε
Semi are of the form :
Terminal Terminal terminal NonTerminal
A CDG is called a Regular Gramma id all its production rules are in one of the following forms :
- Nonterminal semiword
- Nonterminal -> string of terminal
Theorem:
Every Regular Language can be generated by Regular Gramma.
Proof: A regular language is recognised by some NFA. Observe that our construction NFA CFG produces a
regular grammar
Every Regular Grammar generates a Regular Language.
Proof:
Pushdown Automaton:
- A Nondeterministic Finite Automaton with a stack
- Can be used to represent Context Free Language
- The parsers generated by some compiler- compilers are implemented by a Pushdown
Automaton.
a, b → c which means when the machine is reading an a, if there is a b on top of the stack it is popped, and c is
pushed onto the stack.
- If a is ε then no symbol is read from the tape.
- If b is ε then no symbol is popped from the stack.
- If c is ε then no symbol is pushed onto the stack.
Document Summary
Nfa to cfg: name all states in nfa by a symbol, call the start state s, for each edges, for each edge. Write x y: fo each final state x write x write x ax. A cdg is called a regular gramma id all its production rules are in one of the following forms : Every regular language can be generated by regular gramma. Proof: a regular language is recognised by some nfa. Observe that our construction nfa cfg produces a regular grammar. Can be used to represent context free language. The parsers generated by some compiler- compilers are implemented by a pushdown. Automaton. a, (cid:271) (cid:272) (cid:449)hi(cid:272)h (cid:373)ea(cid:374)s (cid:449)he(cid:374) the (cid:373)a(cid:272)hi(cid:374)e is (cid:396)eadi(cid:374)g a(cid:374) a, if the(cid:396)e is a (cid:271) o(cid:374) top of the sta(cid:272)k it is popped, a(cid:374)d (cid:272) is pushed onto the stack. If a is the(cid:374) (cid:374)o s(cid:455)(cid:373)(cid:271)ol is (cid:396)ead f(cid:396)o(cid:373) the tape. If (cid:271) is the(cid:374) (cid:374)o s(cid:455)(cid:373)(cid:271)ol is popped f(cid:396)o(cid:373) the sta(cid:272)k.
