Register

Michael Sipser Edition 3 Exercise 2 Question 33 (Page No. 157)

• edited by
257 views

1 Answer

0 votes
0 votes
but, the given expression is context-free where we can prove it by using PDA in which we push every kth a onto the stack and will pop a for every b. thus, proving it to be context-free.
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
1 answer
1
admin asked May 4, 2019
626 views
Michael Sipser Edition 3 Exercise 2 Question 35 (Page No. 157)
Let $G$ be a $CFG$ in Chomsky normal form that contains $b$ variables$.$ Show that if $G$ generates some string with a derivation having at least $2^{b}$ steps$, L(G)$ is infinite$.$
Let $G$ be a $CFG$ in Chomsky normal form that contains $b$ variables$.$ Show that if $G$ generates some string with a derivation having at least $2^{b}$ steps$, L(G)$ is...
User Avatar
0 votes
0 votes
2 answers
3
admin asked May 4, 2019
674 views
Michael Sipser Edition 3 Exercise 2 Question 32 (Page No. 157)
Let $\Sigma = \{1, 2, 3, 4\}$ and $C = \{w\in\Sigma^{*}\mid$ $\text{in }w,\text{ the number of }1\text{'s equals the number of }2\text{'s, and the number of } 3\text{'s equals the number of }4\text{'s}\}.$ Show that $C$ is not context free.
Let $\Sigma = \{1, 2, 3, 4\}$ and $C = \{w\in\Sigma^{*}\mid$ $\text{in }w,\text{ the number of }1\text{'s equals the number of }2\text{'s, and the number of } 3\text{'s ...
User Avatar
2 votes
2 votes
1 answer
4
admin asked May 4, 2019
1,472 views
Michael Sipser Edition 3 Exercise 2 Question 31 (Page No. 157)
Let $B$ be the language of all palindromes over $\{0,1\}$ containing equal numbers of $0's$ and $1's.$ Show that $B$ is not context free$.$
Let $B$ be the language of all palindromes over $\{0,1\}$ containing equal numbers of $0's$ and $1's.$ Show that $B$ is not context free$.$
User Avatar
Link Copied!