Recent questions tagged peter-linz

Find a pda with fewer than four states that accepts the language $L=${$a^nb^n:n\geq 0$} $\cup$ {$a$}.

Use the CYK method to determine if the string $w = aaabbbbab$ is in the language generated by the grammar $S → aSb|b$.

Use the approach employed in Exercise 2 to show how the CYK membership algorithm can be made into a parsing method.

Use the CYK algorithm to find a parsing of the string $aab$, using the grammar with productions $S\rightarrow AB,$ $A\rightarrow BB|a,$ ...

Use the CYK algorithm to determine whether the strings $aabb, aabba,$ and $abbbb$ are in thelanguage generated by the grammar with productions $S\rightar...

“Two-standard form is general; for any context-free grammar $G$ with $λ ∉ L (G),$ there exists an equivalent grammar in two-standard form.” Prove this.

A context-free grammar is said to be in two-standard form if all production rules satisfy the following pattern $A\rightarrow aBC,$ ...

Convert the grammar $S\rightarrow ABb|a,$ $A\rightarrow aaA|B,$ $B\rightarrow bAb$into Greibach normal form.

Convert the grammar $S\rightarrow ab|aS|aaS$ into Greibach normal form.

Convert the following grammar into Greibach normal form. $S\rightarrow aSb|ab$

Convert the grammar $S\rightarrow aSb|bSa|a|b$ into Greibach normal form.

Show that for every context-free grammar $G = (V, T, S, P)$ there is an equivalent one in which all productions have the form $A → aBC,$or ...

A linear language is one for which there exists a linear grammar[A linear grammar is a grammar in which at most one variable can occur on the right side of any production...

Draw the dependency graph for the grammar in Exercise 4.

Let $G = (V, T, S, P)$ be any context-free grammar without any $λ$-productions or unit-productions.Let $k$ be the maximum number of symbols on the right of any production...

Convert the grammar with productions$S\rightarrow AB|aB,$$A\rightarrow aab|\lambda,$$B\rightarrow bbA$ into Chomsky normal form.

Transform the grammar with productions$S\rightarrow abAB,$$A\rightarrow bAB|\lambda,$$B\rightarrow BAa|A|\lambda$ into Chomsky normal form.

Transform the grammar $S\rightarrow aSaA|A, A\rightarrow abA|b$ into Chomsky normal form.

Convert the grammar $S\rightarrow aSb|ab$ into Chomsky normal form.

Provide the details of the proof of Theorem 6.6.Theorem 6.6Any context-free grammar $G = (V, T, S, P)$ with $λ ∉ L (G)$ has an equivalent grammar $\widehat G=(\widehat V,...

Prove the following counterpart of Exercise 23. Let the set of productions involving the variable $A$ on the left be divided into two disjoint subsets ...

Use the result of the preceding exercise to rewrite the grammar$A\rightarrow Aa|aBc|\lambda,$$B\rightarrow Bb|bc$so that it no longer has productions of the form $A → Ax$...

Prove the following result. Let $G = (V, T, S, P )$ be a context-free grammar. Divide the set of productions whose left sides are some given variable (say, $A$), into two...

A context-free grammar $G$ is said to be minimal for a given language $L$ if $complexity (G) ≤ complexity (\widehat G)$ for any $\widehat{G}$ generating $L$. Show by exam...

It is possible to define the term simplification precisely by introducing the concept of complexity of a grammar. This can be done in many ways; one of them is through th...

Consider the procedure suggested in Theorem 6.2 for the removal of useless productions. Reverse the order of the two parts, first eliminating variables that cannot be rea...

Suppose that a context-free grammar $G = (V, T, S, P)$ has a production of the form $A → xy,$ where $x,y∈ (V\cup T)^+$. Prove that if this rule is replaced by $A\rightarr...

Justify the claim made in the proof of Theorem 6.1 that the variable $B$ can be replaced as soon asit appears.

Show that if a grammar has no $λ$-productions and no unit-productions, then the removal of useless productions by the construction of Theorem 6.2 does not introduce any s...