293 views
1 votes
1 votes

Give informal English descriptions of PDAs for the following languages.

  1. The set of strings over the alphabet $\{a,b\}$ with more $a's$ than $b's$
  2. The complement of the language $\{a^{n}b^{n}|n\geq 0\}$
  3. $\{w\#x|w^{R}$ $\text{is a substring of $x$ for }$ $w,x \in\{0,1\}^{*}\}$
  4. $\{x_{1}\#x_{2}\#...\#x_{k}|k\geq 1,$ $\text{each}$  $ x_{i}\in\{a,b\}^{*},$ $\text{and for some i and }$ $ j,x_{i}=x_{j}^{R}\}$

Please log in or register to answer this question.

Related questions

0 votes
0 votes
0 answers
1
0 votes
0 votes
0 answers
2
admin asked May 1, 2019
964 views
Give an informal description of a pushdown automaton that recognizes the language $A=\{a^{i}b^{j}c^{k}\mid i=j$ $\text{or}$ $ j=k$ $\text{where}$ $ i,j,k\geq 0\}.$
0 votes
0 votes
1 answer
4
admin asked May 1, 2019
531 views
Give a context-free grammar that generates the language $A=\{a^{i}b^{j}c^{k}\mid i=j$ $\text{or}$ $ j=k$ $\text{where}$ $ i,j,k\geq 0\}.$ Is your grammar ambiguous$?$ Why...