Question

Fill out the table described in the polynomial time algorithm for context-free language recognition from $\mathbf{Theorem}\mathbf{7}.\mathbf{16}\mathbf{for}\mathbf{string}\mathbf{w}=\mathbf{baba}\mathbf{and}\mathbf{CFG}\mathbf{G}:$

$$\begin{gathered} \mathbf{S}\to \mathbf{RT} \\ \mathbf{R}\mathbf{\to }\mathbf{T}\mathbf{R}\mathbf{|}\mathbf{a} \\ \mathbf{T}\mathbf{\to }\mathbf{T}\mathbf{R}\mathbf{|}\mathbf{b} \end{gathered}$$

Short answer

The foregoing four-step computation and answer demonstrate that the polynomial algorithm time has been based on correct theory.

Step-by-step solution

Introduction

The term "time complexity" in computer science refers to the computational complexity that quantifies the length of time required to execute an algorithm.

Step – 2: Calculation of polynomial Time algorithm:

i) Solve the Diagonal Algorithm cells i.e.$\left(1,1\right),\left(2,2\right),\left(3,3\right),\left(4,4\right)$

$$\begin{gathered} \left(1,1\right)->b=T, \\ \left(2,2\right)->a=R, \\ \left(3,3\right)->b=T, \\ \left(4,4\right)->a=R \end{gathered}$$

ii) solve$\left(1,2\right)$

$$\begin{gathered} \left(1,1\right)o\left(2,2\right)->TR=\left(R,T\right) \\ \left(2,3\right):\left(2,2\right)o\left(3,3\right)->RT=S \\ \left(3,4\right):\left(3,3\right)o\left(4,4\right)->TR=\left(R,T\right) \end{gathered}$$

iii) Solution$\left(1,3\right):$:

$$\begin{gathered} \left(1,2\right)o\left(3,3\right)->\left\{RToTT\right\}=S \\ \left(2,4\right):\left(2,2\right)o\left(3,4\right)->\left\{RR,RT\right\} \end{gathered}$$

or

$\left(2,3\right)o\left(3,4\right)->\left\{SoR\right\}=S$

iv) Algorithm Solution$\left(1,4\right):$:

$\left(1,1\right)o\left(2,4\right)=\left\{T\right\}o\left\{S\right\}=\varnothing$

or

$\left(1,2\right)o\left(3,4\right)=\left\{R,T\right\}o\left\{R,T\right\}=\left\{RR,RT,TR,TT\right\}=\left(S,R,T\right)$

or

$\left(1,3\right)o\left(4,4\right)=\left\{SoR\right\}=\varnothing$