Register

Ullman (TOC) Edition 3 Exercise 7.4 Question 1 (Page No. 307 - 308)

224 views
0 votes
0 votes

Give algorithms to decide the following$:$

  1. Is $L(G)$ fi nite, for a given CFG  $G?$ Hint$:$ Use the pumping lemma.
  2. Does $L(G)$ contain  at least $100$ strings, for a given CFG $G?$ 
  3. Given a CFG $G$ and one of its variables $A,$ is there any sentential form in which $A$ is the rst symbol. Note$:$ Remember that it is possible for $A$ to appear first in the middle of some sentential form but then for all the symbols to its left to derive $\in.$ 
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
1
admin asked Apr 11, 2019
316 views
Ullman (TOC) Edition 3 Exercise 7.4 Question 5 (Page No. 308)
Modify the $CYK$ algorithm to report the number of distinct parse trees for the given input, rather than just reporting membership in the language$.$
Modify the $CYK$ algorithm to report the number of distinct parse trees for the given input, rather than just reporting membership in the language$.$
User Avatar
0 votes
0 votes
0 answers
2
admin asked Apr 11, 2019
157 views
Ullman (TOC) Edition 3 Exercise 7.4 Question 4 (Page No. 308)
Show that in any $CNF$ grammar all parse trees for strings of length $n$ have $2n-1$ interior nodes $(i.e.,$ $2n-1$ nodes with variables for lables$).$
Show that in any $CNF$ grammar all parse trees for strings of length $n$ have $2n-1$ interior nodes $(i.e.,$ $2n-1$ nodes with variables for lables$).$
User Avatar
0 votes
0 votes
0 answers
3
admin asked Apr 11, 2019
259 views
Ullman (TOC) Edition 3 Exercise 7.4 Question 3 (Page No. 308)
Using the grammar $G$ of Example $7.34,$use the $CYK$ algorithm to determine whether each of the following strings is in $L(G):$ $ababa$ $baaab$ $aabab$
Using the grammar $G$ of Example $7.34,$use the $CYK$ algorithm to determine whether each of the following strings is in $L(G):$$ababa$$baaab$$aabab$
User Avatar
0 votes
0 votes
0 answers
4
admin asked Apr 11, 2019
130 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!