Identify language of given PDA?

1,353

I would argue a bit informally, but in some detail. First note for future reference that the PDA is deterministic. Now let’s see what it accepts.

The initial state is an acceptor state, so it accepts $\epsilon$. Moreover, as long as it reads $a$s, it remains in that state, so it accepts $a^n$ for each $n\ge 0$. Each time it reads an $a$, it pushes an $X$ onto the stack, so after it has read $n$ $a$s, the stack contains $X^nZ$.

Now suppose that after reading $n$ $a$s it reads a $b$. If $n>0$, so that there is an $X$ on top of the stack, it moves to the non-acceptor state and pops an $X$ from the stack; if $n=0$, there is a $Z$ on top of the stack, and it is unable to proceed. We’ll assume for now that $n>0$. If it continues to read $b$s, it remains in the second state and pops one $X$ for each $b$. There is no provision for reading an $a$, and it can move to the third state only when all of the $X$s have been popped off the stack. There were $n$ $X$s on the stack originally, one for each $a$ read, so it must read $n$ $b$s to empty the stack of $X$s and move on to the third state. Thus, it can reach the third state (and be accepted there) if and only if it is of the form $a^nb^n$ for some $n>0$. There is no provision for any further input, so no word extending $a^nb^n$ can be accepted.

This shows that

$$L=\{a^n:n\ge 0\}\cup\{a^nb^n:n\ge 1\}\;,$$

which doesn’t seem to match any of the answers. However, note that $a^0b^0=a^0=\epsilon$, so in fact we can rewrite this as

$$L=\{a^n:n\ge 0\}\cup\{a^nb^n:n\ge 0\}$$

without actually changing the language that we’re describing. And as noted at the beginning, the PDA is deterministic, so (4) is correct.

Share:
1,353

Related videos on Youtube

ً       ً
Author by

ً ً

Updated on August 01, 2022

Comments

  • ً       ً
    ً ً over 1 year

    Consider the transition diagram of a PDA given below with input alphabet $Σ =\{a,b\}$ and stack alphabet $Γ = \{X,Z\}. Z$ is the initial stack symbol. Let $L$ denote the language accepted by the PDA.

    enter image description here

    Which one of the following is TRUE?

    1. $L = \{a^nb^n|n ≥ 0\}$ and is not accepted by any finite automata
    2. $L = \{a^n|n ≥ 0\} ∪ \{a^nb^n|n ≥ 0\}$ and is not accepted by any deterministic PDA
    3. $L$ is not accepted by any Turing machine that halts on every input
    4. $L = \{a^n|n ≥ 0\} ∪ \{a^nb^n|n ≥ 0\}$ and is deterministic context-free

    My attempt :

    I've given option $(1)$ in exam, but somewhere answer is given option $(4)$ which seems correct. That's my silly mistake.

    Can you explain in formal way, please?

  • Brian M. Scott
    Brian M. Scott over 7 years
    @Mithlesh: You're welcome.