Pushdown Automata (PDA)

 A Pushdown Automata (PDA) can be defined as : 

• Q is the set of states
• ∑is the set of input symbols
• Γ is the set of pushdown symbols (which can be pushed and popped from stack)
• q0 is the initial state
• Z is the initial pushdown symbol (which is initially present in stack)
• F is the set of final states
• δ is a transition function which maps Q x {Σ ∪ ∈} x Γ into Q x Γ*. In a given state, PDA will read input symbol and stack symbol (top of the stack) and move to a new state and change the symbol of stack.

Instantaneous Description (ID) 
Instantaneous Description (ID) is an informal notation of how a PDA “computes” a input string and make a decision that string is accepted or rejected. 

A ID is a triple (q, w, α), where: 
1. q is the current state. 
2. w is the remaining input. 
3.α is the stack contents, top at the left. 

   

Turnstile notation 
⊢ sign is called a “turnstile notation” and represents 
one move. 
⊢* sign represents a sequence of moves. 
Eg- (p, b, T) ⊢ (q, w, α) 
This implies that while taking a transition from state p to state q, the input symbol ‘b’ is consumed, and the top of the stack ‘T’ is replaced by a new string ‘α’ 

 Example : Define the pushdown automata for language {anbn | n > 0} 
Solution : M = where Q = { q0, q1 } and Σ = { a, b } and Γ = { A, Z } and δ is given by :

δ( q0, a, Z ) = { ( q0, AZ ) } 
δ( q0, a, A) = { ( q0, AA ) } 
δ( q0, b, A) = { ( q1, ∈) } 
δ( q1, b, A) = { ( q1, ∈) } 

δ( q1, ∈, Z) = { ( q1, ∈) } 

Let us see how this automata works for aaabbb. 

 

Explanation : Initially, the state of automata is q0 and symbol on stack is Z and the input is aaabbb as shown in row 1. On reading ‘a’ (shown in bold in row 2), the state will remain q0 and it will push symbol A on stack. On next ‘a’ (shown in row 3), it will push another symbol A on stack. After reading 3 a’s, the stack will be AAAZ with A on the top. After reading ‘b’ (as shown in row 5), it will pop A and move to state q1 and stack will be AAZ. When all b’s are read, the state will be q1 and stack will be Z. In row 8, on input symbol ‘∈’ and Z on stack, it will pop Z and stack will be empty. This type of acceptance is known as acceptance by empty stack. 

Push Down Automata State Diagram:

 

Note :  

• The above pushdown automaton is deterministic in nature because there is only one move from a state on an input symbol and stack symbol.
• The non-deterministic pushdown automata can have more than one move from a state on an input symbol and stack symbol.
• It is not always possible to convert non-deterministic pushdown automata to deterministic pushdown automata.
• The expressive power of non-deterministic PDA is more as compared to expressive deterministic PDA as some languages are accepted by NPDA but not by deterministic PDA which will be discussed in the next article.
• The pushdown automata can either be implemented using acceptance by empty stack or acceptance by final state and one can be converted to another.

Let’s see the difference between Pushdown Automata and Finite Automata: 

O	Pushdown automata	finite automata
1.	For Type-2 grammar we can design pushdown automata.	For Type-3 grammar we can design finite automata.
2.	Non – Deterministic pushdown automata has more powerful than Deterministic pushdown automata.	Non-Deterministic Finite Automata has same powers as in Deterministic Finite Automata.
3.	Not every Non-Deterministic pushdown automata is transformed into its equivalent Deterministic pushdown Automata .	Every Non-Deterministic Finite Automata is transformed into an equivalent Deterministic Finite Automata
4.	Context free languages can be recognized by pushdown automata.	Regular languages can be recognized by finite automata.
5.	Pushdown automata has the additional stack for storing long sequence of alphabets.	Finite Automata doesn’t has any space to store input alphabets.
6.	It gives acceptance of input alphabets by going up to empty stack and final states.	It accepts the input alphabets by going up to final states.

Context-Free Grammar (CFG)

CFG stands for context-free grammar. It is is a formal grammar which is used to generate all possible patterns of strings in a given formal language. Context-free grammar G can be defined by four tuples as:

1. G = (V, T, P, S)  

Where,

G is the grammar, which consists of a set of the production rule. It is used to generate the string of a language.

T is the final set of a terminal symbol. It is denoted by lower case letters.

Current Time 0:02

/

Duration 18:10

Loaded: 3.30%

 

V is the final set of a non-terminal symbol. It is denoted by capital letters.

P is a set of production rules, which is used for replacing non-terminals symbols(on the left side of the production) in a string with other terminal or non-terminal symbols(on the right side of the production).

S is the start symbol which is used to derive the string. We can derive the string by repeatedly replacing a non-terminal by the right-hand side of the production until all non-terminal have been replaced by terminal symbols.

Example 1:

Construct the CFG for the language having any number of a's over the set ∑= {a}.

Solution:

As we know the regular expression for the above language is

1. r.e. = a*     

2. Production rule for the Regular expression is as follows:

   1. S → aS    rule 1  
   2. S → ε     rule 2  

   Now if we want to derive a string "aaaaaa", we can start with start symbols.

   1.  S  
   2. aS   
   3. aaS          rule 1  
   4. aaaS         rule 1  
   5. aaaaS        rule 1  
   6. aaaaaS       rule 1  
   7. aaaaaaS      rule 1  
   8. aaaaaaε      rule 2  
   9. aaaaaa  

   The r.e. = a* can generate a set of string {ε, a, aa, aaa,.....}. We can have a null string because S is a start symbol and rule 2 gives S → ε.

   Example 2:

   Construct a CFG for the regular expression (0+1)*

   Solution:

   The CFG can be given by,

   1. Production rule (P):  
   2. S → 0S | 1S  
   3. S → ε  

   The rules are in the combination of 0's and 1's with the start symbol. Since (0+1)* indicates {ε, 0, 1, 01, 10, 00, 11, ....}. In this set, ε is a string, so in the rule, we can set the rule S → ε.

3. Example 3:

   Construct a CFG for a language L = {wcwR | where w € (a, b)*}.

   Solution:

   The string that can be generated for a given language is {aacaa, bcb, abcba, bacab, abbcbba, ....}

4. The grammar could be:

   1. S → aSa     rule 1  
   2. S → bSb     rule 2  
   3. S → c       rule 3  

   Now if we want to derive a string "abbcbba", we can start with start symbols.

   1. S → aSa   
   2. S → abSba       from rule 2  
   3. S → abbSbba     from rule 2  
   4. S → abbcbba     from rule 3  

   Thus any of this kind of string can be derived from the given production rules.

   Example 4:

   Construct a CFG for the language L = aⁿb²ⁿ where n>=1.

   Solution:

   The string that can be generated for a given language is {abb, aabbbb, aaabbbbbb....}.

   The grammar could be:

   1. S → aSbb | abb  

   Now if we want to derive a string "aabbbb", we can start with start symbols.

   1. S → aSbb  
   2. S → aabbbb    

   
   

5. Ambiguous Grammar

6. ou can also read our previously discussed article on the Classification of Context-Free Grammar.   Context Free Grammars(CFGs) are classified based on:

   • Number of Derivation trees
   • Number of strings

     Depending on the Number of Derivation trees, CFGs are sub-divided into 2 types:

   • Ambiguous grammars
   • Unambiguous grammars

   Ambiguous grammar:   A CFG is said to be ambiguous if there exists more than one derivation tree for the given input string i.e., more than one LeftMost Derivation Tree (LMDT) or RightMost Derivation Tree (RMDT).   Definition: G = (V,T,P,S) is a CFG that is said to be ambiguous if and only if there exists a string in T* that has more than one parse tree. where V is a finite set of variables. T is a finite set of terminals. P is a finite set of productions of the form, A -> α, where A is a variable and α ∈ (V ∪ T)* S is a designated variable called the start symbol.

7. For Example:

8. Let us consider this grammar: E -> E+E|id We can create a 2 parse tree from this grammar to obtain a string id+id+id. The following are the 2 parse trees generated by left-most derivation: 

9. 
   
   

   

   
   
   
   
   

10. Both the above parse trees are derived from the same grammar rules but both parse trees are different. Hence the grammar is ambiguous.     2. Let us now consider the following grammar:  

    Set of alphabets ∑ = {0,…,9, +, *, (, )}
    
    E -> I        
    E -> E + E
    E -> E * E
    E -> (E)
    I -> ε | 0 | 1 | … | 9
     

    From the above grammar String 3*2+5 can be derived in 2 ways:  

    I) First leftmost derivation                   II) Second leftmost derivation
            E=>E*E                          E=>E+E
             =>I*E                           =>E*E+E
             =>3*E+E                                       =>I*E+E
             =>3*I+E                           =>3*E+E
             =>3*2+E                           =>3*I+E
             =>3*2+I                           =>3*2+I
             =>3*2+5                           =>3*2+5

      Following are some examples of ambiguous grammar:  

    • S-> aS |Sa| Є
    • E-> E +E | E*E| id
    • A -> AA | (A) | a
    • S -> SS|AB , A -> Aa|a , B -> Bb|b

    Whereas following grammars are unambiguous:  

    • S -> (L) | a, L -> LS | S
    • S -> AA , A -> aA , A -> b

    Inherently ambiguous Language:     Let L be a Context Free Language (CFL). If every Context-Free Grammar G with Language L = L(G) is ambiguous, then L is said to be inherently ambiguous Language. Ambiguity is a property of grammar not languages. Ambiguous grammar is unlikely to be useful for a programming language because two parse tree structures(or more) for the same string(program) imply two different meanings (executable programs) for the program. An inherently ambiguous language would be absolutely unsuitable as a programming language because we would not have any way of fixing a unique structure for all its programs. For example,

    L = {anbncm} ∪ {anbmcm}