Week 6 Lecture 1 - CFGs and FSAs & Pushdown Stack Automata

What is a semiword?

For a given CFG, a string of terminals (maybe none) concatenated with exactly 1 non-terminal on the right.

What is a semipath?

For a given FSA, it is a string of input symbols (maybe non) that have been read, followed by a state on the right.

Prove every word accepted by the FSA is generated by the CFG.

Consider abbaa:

Construct the path through the FSA to an accepting state through a sequence of semipaths. These are formed from the string read from the input followed by the name of the state to which the string takes us.

Prove every word accepted by the CFG is generated by the FSA.

Prove every word accepted by the CFG is generated by the FSA by construction (draw an FSA)

Write down a regular grammar for generating a*b*

What is the “memory” in an FSA?

Consists of knowing which of the finite number of states it is currently in. It doesn’t know how it got to that state.

Since the need for storage in an FSA is not sufficient for non-regular languages, what is used?

Stacks

What does x/ys mean for stacks in non-regular languages?

If x is on top of the stack then pop it and push ys
onto the stack

What is a Pushdown Stack Automaton (NPDA) and how does it use a stack?

Like an NFDA (with λ transitions permitted) but it also has a potentially infinite stack.

Can only observe the stack symbol at the top of the stack. Uses this and the input symbol to make a transition to another state and replaces the top of the stack by another string of stack symbols.

Acceptance in an NPDA

Thought to have accepting states. An input string is accepted if after processing the whole of the input string, moving from state to state and adjusting the stack, the machine may end up in an accepting state.

What are the 7 components in an NPDA?

⟨Q, Σ, Γ, δ, q₀, z₀, F ⟩

δ in an NPDA?

The NPDA is non-deterministic, so the result type is a set of states — we define δ as a function to a set of pairs of states and sequences of stack symbols.

As inputs, δ takes a state q ∈ Q, an input symbol a ∈ (Σ ∪ {λ}), and a stack symbol z ∈ Γ. So, when the automaton is in a particular state, the decision about which transition to take is based on the input symbol a and the top symbol of the stack z.

Effects of a transition onto a new state in an NPDA (δ)

The effect of a transition to a new state is that z is removed from the top of stack, and replaced with the relevant string of stack symbols. If the stack symbol is just to be popped then the replacement string will be empty λ.

What does a, 0/10 mean?

The transition should be taken on input a, when the top stack symbol is 0. This 0 is replaced with 10, ie 1 is pushed onto the stack.

What are the key transitions?