Register

Michael Sipser Edition 3 Exercise 2 Question 19 (Page No. 156)

• edited by
320 views
0 votes
0 votes

Let $CFG$   $G$ be the following grammar$.$

  •  $S\rightarrow aSb \mid bY \mid Y a$
  • $Y\rightarrow bY \mid aY \mid \epsilon$

Give a simple description of $L(G)$ in English$.$ Use that description to give a $CFG$ for $\overline{L(G)},$ the complement of $L(G).$

• edited by
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
1 answer
1
admin asked May 4, 2019
271 views
Michael Sipser Edition 3 Exercise 2 Question 21 (Page No. 156)
Let $\Sigma = \{a,b\}.$ Give a $CFG$ generating the language of strings with twice as many $a’s$ as $b’s.$ Prove that your grammar is correct$.$
Let $\Sigma = \{a,b\}.$ Give a $CFG$ generating the language of strings with twice as many $a’s$ as $b’s.$ Prove that your grammar is correct$.$
User Avatar
0 votes
0 votes
1 answer
3
admin asked May 4, 2019
380 views
Michael Sipser Edition 3 Exercise 2 Question 22 (Page No. 156)
Let $C = \{x\#y \mid x, y\in\{0,1\}^{*}$ and $x\neq y\}.$ Show that $C$ is a context-free language$.$
Let $C = \{x\#y \mid x, y\in\{0,1\}^{*}$ and $x\neq y\}.$ Show that $C$ is a context-free language$.$
User Avatar
0 votes
0 votes
1 answer
4
admin asked May 4, 2019
1,986 views
Michael Sipser Edition 3 Exercise 2 Question 14 (Page No. 156)
Convert the following $\text{CFG}$ into an equivalent $\text{CFG}$ in Chomsky normal form,using the procedure given in $\text{Theorem 2.9.}$ $A\rightarrow BAB \mid B \mid \epsilon$ $B\rightarrow 00 \mid \epsilon$
Convert the following $\text{CFG}$ into an equivalent $\text{CFG}$ in Chomsky normal form,using the procedure given in $\text{Theorem 2.9.}$$A\rightarrow BAB \mid B \mid ...
User Avatar
Link Copied!