CFG Recognition

Given a grammar GG and a string ss, determine if the string ss can be derived by the grammar GG.

Parameters

  • nn: length of the given string
  • ∣G∣|G|: size of the grammar

Related Problems

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 2 of 2 algorithms

See more
Valiant1975O(nω∣G∣)O(n^{\omega} |G|)O(n2)O(n^2)
Cocke–Younger–Kasami algorithm1968O(n3∣G∣)O(n^3 |G|)O(n2)O(n^2)

Reductions Table

Displaying 2 of 2 reductions

Other relevant algorithms

Insuffient Data to display table