Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
Syntax and Semantics

INF2: Syntax and Semantics 2003
Lecture 7

Syntax and Semantics

Topics

In our previous lecture, we introduced the formalism of pushdown automata (PDA), and devised automata to accept some nonregular languages. In this lecture, we shall study the connections between PDA and context-free grammars. In particular, we shall argue that PDA accept precisely the context-free languages.

Time and Location

Thursday, 27 February 2003 at 10:15 in A4-106.

Reading Material

Primary Reading: Section 2.2 of Introduction to the Theory of Computation by Michael Sipser.

Exercises

Exercise 2.11 on pages 121 of Introduction to the Theory of Computation by Michael Sipser.
Exercise 2.13 on page 121 of Introduction to the Theory of Computation by Michael Sipser.
- What would happen if the first production in that grammar were replaced by S --> T?
- Can you give a pushdown automaton that recognizes the language generated by the grammar in exercise 2.13?
Is the class of context-free languages closed under the reverse operation? Argue for your answer.
Given a pushdown automaton M, how would you build a pushdown automaton star(M) that accepts the star of the language accepted by M?

Luca Aceto, Institute of Computer Science, Aalborg University.

Last modified: .

INF2: Syntax and Semantics 2003 Lecture 7

Topics

Time and Location

Reading Material

Exercises

INF2: Syntax and Semantics 2003
Lecture 7