Register

Michael Sipser Edition 3 Exercise 2 Question 5 (Page No. 155)

853 views
0 votes
0 votes

Give informal descriptions and state diagrams of pushdown automata for the languages in the following languages In all parts, the alphabet $\sum$ is $\{0,1\}.$

  1. $\text{{w| w contains at least three 1’s}}$
  2. $\text{{w| w starts and ends with the same symbol}}$
  3. $\text{{w| the length of w is odd}}$
  4. $\text{{w| the length of w is odd and its middle symbol is a 0}}$
  5. $\text{{$w|w=w^{R},$that is, w is a palindrome}}$
  6. $\text{The empty set}.$
User Avatar

Please log in or register to answer this question.

Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
0 answers
1
admin asked May 1, 2019
301 views
Michael Sipser Edition 3 Exercise 2 Question 11 (Page No. 155)
Convert the $CFG$ $G_{4}$ $E\rightarrow E+T\mid T$ $T\rightarrow T\times F\mid F$ $F\rightarrow (E)\mid a$ to an equivalent $PDA,$ using the procedure given in $\text{Theorem 2.20.}$
Convert the $CFG$ $G_{4}$ $E\rightarrow E+T\mid T$$T\rightarrow T\times F\mid F$$F\rightarrow (E)\mid a$ to an equivalent $PDA,$ usin...
User Avatar
0 votes
0 votes
0 answers
2
admin asked May 1, 2019
989 views
Michael Sipser Edition 3 Exercise 2 Question 10 (Page No. 155)
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\}.$
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\}.$
User Avatar
0 votes
0 votes
1 answer
4
admin asked May 1, 2019
555 views
Michael Sipser Edition 3 Exercise 2 Question 9 (Page No. 155)
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 or why not$?$
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...
User Avatar
Link Copied!