Michael Sipser Edition 3 Exercise 2 Question 52 (Page No. 159)

22 views
Show that every DCFG generates a prefix-free language.

Related questions

1
20 views
Show that every DCFG is an unambiguous CFG.
Show that $EQ_{CFG}$ is co-Turing-recognizable.
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.
Show that if $G$ is a $CFG$ in Chomsky normal form$,$ then for any string $w\in L(G)$ of length $n\geq 1,$ exactly $2n − 1$ steps are required for any derivation of $w.$