Question

Modify the algorithm for context-free language recognition in the proof of Theorem 7.16 to give a polynomial time algorithm that produces a parse tree for a string, given the string and a CFG, if that grammar generates the string.

Short answer

The algorithm can be modified for context-free language recognition. The modified algorithm is provided.

Step-by-step solution

Step-1: Context-free language

Context free language is generated by the context free grammar. A language is said to be context free , if it is accepted by the push down automata.

Explain the given information.

Consider a parse tree of any grammar $G=\left(V,T,R,S\right)$ ,

Where, $S$start symbol is a root abd the $V$ non-terminals are interior nodes and the terminals $T$ represents the leaf nodes of the parse tree.

Each terminal string generated by grammar G has parse tree.

 Step 3: Modified Algorithm

The Theorem 7.16 states that every context free languages is a member of class P. The modified algorithm to produce a polynomial time algorithm is as follows,

Modified Algorithm:

$D=$“On input$s=s_1{s}_2\dots s_n$ and CFG G

$\text{ParseTree}\leftarrow \left(\text{Initial}S \text{tree}, \text{Beginning} \text{of} \text{the} \text{string} s\right)$

$\text{CurrentState}\leftarrow \text{POP the ParseTree}$

repeat for $i=1,2,3,4,\dots n$

if parsing is successful for CurrentState

return TREE(CurrentState)

else

if no nodes to expand

return reject

else

$temp\leftarrow \text{Apply the CFG} \text{rules} \text{on} \text{CurrentState}$

PUSH temp into the Parse Tree

if ParseTree is empty

return reject

else

$\text{CurrentState}\leftarrow \text{NEXT}\left(\text{ParseTree}\right)$

returnParseTree

The above algorithm takes the string and apply the rules on it. For each part of the string rules are applied and the next node is found.

Each state is added to the tree. If the input is processed completely then it returns the parse tree.

Therefore, the modified algorithm has been provided.