Register

Ullman (TOC) Edition 3 Exercise 7.3 Question 2 (Page No. 297)

• edited by
106 views
0 votes
0 votes

Consider the following languages$:$

$L_{1}=\{a^{n}b^{2n}c^{m}|n,m\geq 0\}$
$L_{2}=\{a^{n}b^{m}c^{2m}|n,m\geq 0\}$

  1. Show that each of these languages is context-free by giving grammars for each.
  2. Is $L_{1}\cap L_{2}$ a $CFL?$ Justify your answer.
• 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
0 answers
2
admin asked Apr 11, 2019
124 views
Ullman (TOC) Edition 3 Exercise 7.3 Question 3 (Page No. 297)
Show that the $CFL's$ are not closed under the following operations$:$ $\text{min}$ $\text{max}$ $\text{half}$ $\text{alt}$
Show that the $CFL's$ are not closed under the following operations$:$$\text{min}$$\text{max}$$\text{half}$$\text{alt}$
User Avatar
0 votes
0 votes
0 answers
3
admin asked Apr 11, 2019
114 views
Ullman (TOC) Edition 3 Exercise 7.3 Question 1 (Page No. 297)
Show that the $CFL's$ are closed under the following$:$ $\text{init},$ Hint$:$ Start with a $CNF$ grammar for the language $L.$ $\text{The operation $L/a,$}$ Hint$:$ Again,start with a $CNF$ grammar for $L.$ $\text{cycle, }$ Hint$:$ Try a $PDA-$based constrction.
Show that the $CFL's$ are closed under the following$:$$\text{init},$ Hint$:$ Start with a $CNF$ grammar for the language $L.$$\text{The operation $L/a,$}$ Hint$:$ Again...
User Avatar
0 votes
0 votes
0 answers
4
admin asked Apr 11, 2019
128 views
Ullman (TOC) Edition 3 Exercise 7.4 Question 2 (Page No. 308)
Use the technique described in Section $7.4.3$ to develop linear time algorithms for the following questions about $CFG's:$ Which symbols appear in some sentential form$?$ Which symbols are nullable $\text{(derive $\in$)?}$
Use the technique described in Section $7.4.3$ to develop linear time algorithms for the following questions about $CFG's:$ Which symbols appear in some sentential form$?...
User Avatar
Link Copied!