Question

Give informal English descriptions of PDAs for the languages in Exercise 2.6

Give context-free grammars generating the following languages.

a. The set of strings over the alphabet $\left\{a,b\right\}$with more a's than b's

b. The complement of the language $\left\{a^n\right.b^n\overline{)n\ge 0}\left.\right\}$.

c. $\left\{w\#x\overline{)w^R}\right.$is a substring of x for w,x $\in \left\{0,1\right\}*\left.\right\}$

d. $\left\{\right.$localid="1662105288591" $x_1\#x_2\#...\#x_k\overline{)k\ge 1,}$each xilocalid="1662105304877" $\in \left\{a,b\right\}*,$and for some i and j ,localid="1662105320570" $x_i=x_j^R$

Short answer

1. The informal english descriptions of pushdown deterministic automata for the language $\left\{a,b\right\}$,a's than b's is given below.
2. The informal english descriptions of pushdown deterministic automata for the language $\left\{a^n{b}^n\overline{)n\ge 0}\right\}$is given below.
3. The informal english descriptions of pushdown deterministic automata for the language $\left\{w\#x\overline{)w^R}\right.$is a substring of x for w,x $\in \left\{0,1\right\}*\left.\right\}$is given below.
4. The informal english descriptions of pushdown deterministic automata for the language$\left\{x_1\#x_2\#...\#x_k\overline{)k\ge 1,each{x}_i\in \left\{a,b\right\}*}\right\}$and for some i and j ,$x_i={x_j}^R$ is given below.

Step-by-step solution

Define PDA

Pushdown Automata is a finite automata with extra memory called stack which helps Pushdown automata to recognize Context Free Languages. Context free language is a grammar where its language or string that formed by context free grammar is supports pushdown deterministic automata. Context free grammar is used to generate context free languages. A context free grammar is a formal grammar which is used to generate all the possible patterns of strings in a given formal language. And it is contained number of sets of production rules.

Explanation

a)

The informal english descriptions ofpushdown deterministic automatafor the language$\left\{a,b\right\}$, a's than b's is given below.

The pushdown deterministic automata uses its stack to count the number of a's minus the number of b's . It enters an accepting state whenever this count is positive. In more detail, it operates as follows.

The pushdown deterministic automata scan across the input. If it sees a b's and its top stack symbol is an a, it pops the stack.

Similarly, if it scans an a and its top stack symbol is a b, it pops the stack. In all other cases, it pushes the input symbol onto the stack.

After the pushdown deterministic automata finishes the input, if a is on top of the stack, it accepts. Otherwise it rejects.

Explanation of part (b).

b)

The informal english descriptions ofpushdown deterministic automatafor the language$\left\{a^n{b}^n\overline{)n\ge 0}\right\}$is given below.

For the complement of the language,$\left\{a^n{b}^n\overline{)n\ge 0}\right\}$.

Push the $ onto the stack so that we know when we are at the empty stack. If the stack is empty or there is an’a’ at the top of the stack, and we read an ’a ’, then push an ’a ’ onto the stack for each a that is read on the input string.

If the stack is empty, or there is a ’b’ at the stop of the stack and we read a ’b ’, then push two ’b’s onto the stack for each ’b’ that is read. If there are two ’a” s at the top of the stack, and we read a ’b’, then pop the two’a ” s as we read the ’b’.

Otherwise if there is only one ’a ’ on the top of the stack, pop that ’a’ and push one ’b’ onto the stack. If there is a ’b’ at the top of the stack and we read an ’a’, the pop the ’b’ for each ’a ’ that is read.

Finally, if the top of the stack is the dollar sign, then non-deterministically branch (without reading any new input) to the accept state.

Explanation of part (c).

(c)

The informal english descriptions ofpushdown deterministic automatafor the language$\{w\#x\overline{)w^R}$is a substring of x for w, x$\mathbf{\in }\left\{0,1\right\}\mathbf{*}\}$is given below.

$\{w\#x\overline{)w^R}$is a substring of x for w, x $\mathbf{\in }\left\{0,1\right\}\mathbf{*}\}$

The pushdown deterministic automata scans across the input string and pushes every symbol it reads until it reads a# .

If a# is never encountered, it rejects. Then, the pushdown deterministic automata skip over part of the input, non deterministically deciding when to stop skipping.

At that point, it compares the next input symbols with the symbols it pops off the stack. At any disagreement, or if the input finishes while the stack is nonempty, this branch of the computation rejects.

If the stack becomes empty, the machine reads the rest of the input and accepts.

Explanation of part (d).

d)

The informal english descriptions ofpushdown deterministic automatafor the language$\left\{x_1\#x_2\#...\#X_k\overline{)k\ge 1,each{x}_i}\in \left\{a,b\right\}*\right\}$, and for some i and j,${\mathit{x}}_{\mathbf{i}}\mathbf{=}{{\mathbf{x}}_{\mathbf{j}}}^{\mathbf{R}}$is given below.

The pushdown deterministic automata uses its stack to count the number of a's minus the number of b's. It enters an accepting state whenever this count is positive. In more detail, it operates as follows.

The pushdown deterministic automata scan across the input. If it sees a b'sand its top stack symbol is an a, it pops the stack.

Similarly, if it scans an a and its top stack symbol is ab, it pops the stack. In all other cases, it pushes the input symbol onto the stack.

After the pushdown deterministic automata finishes the input, ifa is on top of the stack, it accepts. Otherwise it rejects.

$\{x_1\#x_2\#...\#x_k\overline{)k\ge 1,}$each${\mathit{x}}_{\mathbf{i}}\mathbf{\in }\left\{a,b\right\}\mathbf{*}\mathbf{,}$and for some i and j ,${\mathit{x}}_{\mathbf{i}}\mathbf{=}{{\mathbf{x}}_{\mathbf{j}}}^{\mathbf{R}}$