Acceptance Criteria for PDA

There are two possible acceptance criteria for PDA:

1. acceptance by empty stack
2. acceptance by final state.

The two are easily shown to be equivalent: a final state can perform a pop loop to get to an empty stack, and a machine can detect an empty stack and enter a final state by detecting a unique symbol pushed by the initial state.

Some use a 6-tuple, dropping the Ω for the initial stack symbol, instead adding a first transition which writes a start symbol to the stack.

Tomorrow, we will see formal definition of “Deterministic Push down Automata” (DPDA).

Context-Free-Language (CFL)

A language L is said to be a Context-Free-Language (CFL) if its grammar is Context-Free. More precisely, it is a language whose words, sentences and phrases are made of symbols and words from a Context-Free-Grammar. Usually, CFL is of the form L=L(G). Given below are examples for CFG but not for CFL.
Here I am giving you one example of context-free grammar
Example:
A context-free grammar for the language consisting of all strings over {a,b} which contain a different number of a's to b's is
S → U | V
U → TaU | TaT
V → TbV | TbT
T → aTbT | bTaT | ε
Here, T can generate all strings with the same number of a's as b's, U generates all strings with more a's than b's and V generates all strings with fewer a's than b's.

Automata Step by Step

Let’s see the definitions of “String”, “Alphabet”,” Sequence” and “Language”. Remember all above terms are connected. You can’t understand any of them without knowing the definitions of all of them.

String:

In computer programming and formal language theory, (and other branches of mathematics), a string is an ordered sequence of symbols. These symbols are chosen from a predetermined set.

Example: Empty String (contains no symbols)

Length of Empty String is zero.

Now we will define “Alphabet”.

Alphabet:
An alphabet is a finite set of symbols.
Examples:
Binary Alphabet = {0, 1}
Unary alphabet= {1}
ASCII Alphabet= {…..A, B, C………, a, b, c…………}
Decimal Alphabet= {0, 1, 2…….8, 9}