Register

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

• edited by
220 views

1 Answer

0 votes
0 votes
S->aaAb | aBbbb | C | D

A->aAb | aA | a

B->aBb | a

C->aA | a

D->bB | b
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
621 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
669 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
0 votes
0 votes
0 answers
4
admin asked May 4, 2019
389 views
Michael Sipser Edition 3 Exercise 2 Question 25 (Page No. 157)
For any language $A,$ let $SUFFIX(A) = \{v\mid uv \in A$ $\text{for some string u\}}.$ Show that the class of context-free languages is closed under the $\text{SUFFIX operation.}$
For any language $A,$ let $SUFFIX(A) = \{v\mid uv \in A$ $\text{for some string u\}}.$ Show that the class of context-free languages is closed under the $\text{SUFFIX ope...
User Avatar
Link Copied!