Understanding context free grammars in conjunction with PDA

Question

I have read TONS of articles about context free grammars and Pushdown Automata but I think there are things that I dont seem to understand. I am not studying computer science but I am really interested in many of the topics and I hope you can help me realign my knowledge about the CFG and PDA.

So my question is: could you tell me if what im writing here is correct? If not could you tell me what is wrong in my interpretation?

What I think I understood:

A state of a pushdown automata is equivalent to a set of production rules (or is it a production rule?) and these production rules contain replacement rules.

Depending on what character we read from our input we add an appropiate stack character or replace a character in the stack which is defined by one of the replacement rules.

So lets say we have defined the following production rule: a^n b^m : m != n

the replacement rules looks like:

production rule {
    input ; Stack Symbol -> To Do On Stack

    a ; nothing -> A
    a ; A -> AA
    b ; A -> nothing
    emtpy -> #
}

for every "a" we read we add an A and for every "b" we remove an A. The stuff what happens in my PDA stack is therefore defined in the replacement rule of my production rule?

Now if I wanted to parse a nested input like: "{hello world {fooBar is cool + 5}}"

I assume I need two production rules each with different replacement rules for our stack:

RULE 1:

{ ; nothing -> O
[a-zA-Z] ; O -> L

ok seriously I have to stop here because I have no idea what im doing. I would appreciate it if you could tell if my interpretation is wrong and how to handle the last example.

I am sorry if I couldnt be more concise. Im currently a bit confused with this.

Answer 1

A PDA is a machine with a certain set of states and an infinite, initially empty, stack. It also has an input tape with the input word written on it. As long as there's input remaining, the machine reads the next character of input, checks its current state, and pops off the top character of the stack to read it. Based on what it finds, the PDA then switches into some new state and pushes a new character onto the stack.

The set of all languages PDAs can recognize is called the context-free languages. They are context-free roughly because what happens next depends only on the character at the top of the stack, rather than all the context beneath it in the stack. A PDA is finished when it goes into a special state for accepting or rejecting the input word. (Some people instead say that a PDA is finished when the stack is empty.) The language of a PDA is the set of all words that it accepts.

---

A context free grammar is a set of production rules. For simplicity, a production rule looks like $A \mapsto B$ or $A\mapsto BC$ or $A \mapsto \mathtt{a}$ or $A \mapsto \epsilon$. These respectively mean "If you have the symbol $A$, you may replace it with $B$ / $BC$ / the character $\mathtt{a}$ / the empty string." A production rule is a rule that allows you to transform a symbol. The capital letter symbols are called nonterminals; they are sort of like variables. The symbols like $\mathtt{a}$ are terminals; they are sort of like constants. There is a special nonterminal symbol called the start symbol, usually denoted $S$. The language of a context-free grammar (set of rules) is the set of all strings of terminals (like $\mathtt{abcde}$) you can make starting from the start symbol $S$ and applying any of the rules until only terminal symbols remain.

---

It turns out that context-free grammars (CFGs) are equivalent to pushdown automata (PDAs) because they can recognize the same languages. In particular, for every CFG there's a corresponding PDA, and vice versa.

Here's the CFG->PDA recipe. If you have a CFG, make a PDA with one start state and one reject state. Push the start symbol onto the stack. Then, loop: pop off the top symbol of the stack. Nondeterministically pick a production rule with that symbol on the left hand side. Push all the symbols on the right hand side of that rule onto the stack (make sure the leftmost symbol ends upon top). If the symbol at the top of the stack is a terminal character, make sure it matches the next character of input, otherwise reject. If the stack becomes empty, accept.