Register

Michael Sipser Edition 3 Exercise 2 Question 44 (Page No. 158)

• edited by
291 views
0 votes
0 votes
If $A$ and $B$ are languages, define $A \diamond B = \{xy \mid x \in A\: \text{and}\: y \in B \;\text{and}  \mid x \mid = \mid y \mid \}$. Show that if $A$ and $B$ are regular languages, then $A \diamond B$ is a CFL.
• edited by
User Avatar

1 Answer

0 votes
0 votes

Suppose,  A = { 0^n | n > 0 }    and

                 B = { 1^n | n > 0 }

     By def. of a and b having  any no of 0s and 1s repectively

 both are regular languages

BUT,   A ∘ B = { 0^n.1^n  | n >0 }

         which is a renowned  cfl .

same applies for →  B∘A

User Avatar
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 Oct 12, 2019
421 views
Michael Sipser Edition 3 Exercise 2 Question 46 (Page No. 158)
Consider the following CFG $G:$ $S \rightarrow SS \mid T$ $T \rightarrow aT b \mid ab$ Describe $L(G)$ and show that $G$ is ambiguous. Give an unambiguous grammar $H$ where $L(H) = L(G)$ and sketch a proof that $H$ is unambiguous.
Consider the following CFG $G:$$S \rightarrow SS \mid T$$T \rightarrow aT b \mid ab$Describe $L(G)$ and show that $G$ is ambiguous. Give an unambiguous grammar $H$ where ...
User Avatar
0 votes
0 votes
0 answers
2
admin asked Oct 12, 2019
244 views
Michael Sipser Edition 3 Exercise 2 Question 45 (Page No. 158)
Let $A = \{wtw^{R}\mid w,t\in\{0,1\}^{\ast}\:\text{and} \mid w \mid = \mid t \mid \}$. Prove that $A$ is not a CFL.
Let $A = \{wtw^{R}\mid w,t\in\{0,1\}^{\ast}\:\text{and} \mid w \mid = \mid t \mid \}$. Prove that $A$ is not a CFL.
User Avatar
0 votes
0 votes
0 answers
4
admin asked Oct 12, 2019
167 views
Michael Sipser Edition 3 Exercise 2 Question 42 (Page No. 158)
Let $Y = \{w\mid w = t_{1}\#t_{2}\#\dots t_{k} \:\text{for}\: k\geq 0,\text{each}\: t_{i}\in 1^{\ast}, \text{and}\: t_{i}\neq t_{j} \text{whenever}\: i\neq j\}$.Here $\Sigma = \{1,\#\}$. Prove that $Y$ is not context free.
Let $Y = \{w\mid w = t_{1}\#t_{2}\#\dots t_{k} \:\text{for}\: k\geq 0,\text{each}\: t_{i}\in 1^{\ast}, \text{and}\: t_{i}\neq t_{j} \text{whenever}\: i\neq j\}$.Here $\Si...
User Avatar
Link Copied!