CYK algorithm - Revision history

2601:647:6700:45F0:2982:A084:FC77:CD99: /* Standard form */ clarification on the empty string

2024-08-03T06:15:46Z

Standard form: clarification on the empty string

← Previous revision		Revision as of 06:15, 3 August 2024
Line 18:		Line 18:
	==Standard form==		==Standard form==

	The [[dynamic programming]] algorithm requires the context-free grammar to be rendered into [[Chomsky normal form]] (CNF), because it tests for possibilities to split the current sequence into two smaller sequences. Any context-free grammar that does not generate the empty string can be represented in CNF using only [[Formal grammar#The syntax of grammars\|production rules]] of the forms <math>A\rightarrow \alpha</math>, <math>A\rightarrow B C</math>, ~~and~~ <math>S\to \varepsilon</math> where <math>S</math> is the start symbol.<ref>{{Cite book \|last=Sipser \|first=Michael \|url=https://www.worldcat.org/oclc/58544333 \|title=Introduction to the theory of computation \|date=2006 \|publisher=Thomson Course Technology \|isbn=0-534-95097-3 \|edition=2nd \|location=Boston \|at=Definition 2.8 \|oclc=58544333}}</ref>		The [[dynamic programming]] algorithm requires the context-free grammar to be rendered into [[Chomsky normal form]] (CNF), because it tests for possibilities to split the current sequence into two smaller sequences. Any context-free grammar that does not generate the empty string can be represented in CNF using only [[Formal grammar#The syntax of grammars\|production rules]] of the forms <math>A\rightarrow \alpha</math> and <math>A\rightarrow B C</math>; to allow for the empty string, one can explicitly allow <math>S\to \varepsilon</math>, where <math>S</math> is the start symbol.<ref>{{Cite book \|last=Sipser \|first=Michael \|url=https://www.worldcat.org/oclc/58544333 \|title=Introduction to the theory of computation \|date=2006 \|publisher=Thomson Course Technology \|isbn=0-534-95097-3 \|edition=2nd \|location=Boston \|at=Definition 2.8 \|oclc=58544333}}</ref>

	==Algorithm==		==Algorithm==

MikeKrueg: Made link available also in english version

2024-03-15T14:28:55Z

Made link available also in english version

← Previous revision		Revision as of 14:28, 15 March 2024
Line 170:		Line 170:

	==External links==		==External links==
			* [https://raw.org/tool/cyk-algorithm/ Interactive Visualization of the CYK algorithm]
	* [https://martinlaz.github.io/demos/cky.html CYK parsing demo in JavaScript]		* [https://martinlaz.github.io/demos/cky.html CYK parsing demo in JavaScript]
	* [https://www.swisseduc.ch/informatik/exorciser/ Exorciser is a Java application to generate exercises in the CYK algorithm as well as Finite State Machines, Markov algorithms etc]		* [https://www.swisseduc.ch/informatik/exorciser/ Exorciser is a Java application to generate exercises in the CYK algorithm as well as Finite State Machines, Markov algorithms etc]

MrOllie: Reverted 1 edit by Choltreppe (talk): WP:ELNO

2024-02-09T19:18:26Z

Reverted 1 edit by Choltreppe (talk): WP:ELNO

← Previous revision		Revision as of 19:18, 9 February 2024
Line 170:		Line 170:

	==External links==		==External links==
	* [https://lamboolda.com/parsing#0 online CYK parsing]
	* [https://martinlaz.github.io/demos/cky.html CYK parsing demo in JavaScript]		* [https://martinlaz.github.io/demos/cky.html CYK parsing demo in JavaScript]
	* [https://www.swisseduc.ch/informatik/exorciser/ Exorciser is a Java application to generate exercises in the CYK algorithm as well as Finite State Machines, Markov algorithms etc]		* [https://www.swisseduc.ch/informatik/exorciser/ Exorciser is a Java application to generate exercises in the CYK algorithm as well as Finite State Machines, Markov algorithms etc]

Choltreppe at 22:18, 10 January 2024

2024-01-10T22:18:44Z

← Previous revision		Revision as of 22:18, 10 January 2024
Line 170:		Line 170:

	==External links==		==External links==
			* [https://lamboolda.com/parsing#0 online CYK parsing]
	* [https://martinlaz.github.io/demos/cky.html CYK parsing demo in JavaScript]		* [https://martinlaz.github.io/demos/cky.html CYK parsing demo in JavaScript]
	* [https://www.swisseduc.ch/informatik/exorciser/ Exorciser is a Java application to generate exercises in the CYK algorithm as well as Finite State Machines, Markov algorithms etc]		* [https://www.swisseduc.ch/informatik/exorciser/ Exorciser is a Java application to generate exercises in the CYK algorithm as well as Finite State Machines, Markov algorithms etc]

Ykhwong: Add {{Redirect|CYK||Cyk (disambiguation)}}

2023-12-18T12:34:42Z

Add {{Redirect|CYK||Cyk (disambiguation)}}

← Previous revision		Revision as of 12:34, 18 December 2023
Line 1:		Line 1:
	{{Short description\|Parsing algorithm for context-free grammars}}		{{Short description\|Parsing algorithm for context-free grammars}}
			{{Redirect\|CYK\|\|Cyk (disambiguation)}}
	{{Infobox algorithm		{{Infobox algorithm
	\|name=Cocke–Younger–Kasami algorithm (CYK)		\|name=Cocke–Younger–Kasami algorithm (CYK)

Sammi Brie: Importing Wikidata short description: "Parsing algorithm for context-free grammars"

2023-12-15T20:53:28Z

Importing Wikidata short description: "Parsing algorithm for context-free grammars"

← Previous revision		Revision as of 20:53, 15 December 2023
Line 1:		Line 1:
			{{Short description\|Parsing algorithm for context-free grammars}}
	{{Infobox algorithm		{{Infobox algorithm
	\|name=Cocke–Younger–Kasami algorithm (CYK)		\|name=Cocke–Younger–Kasami algorithm (CYK)

2A00:1028:8396:4C9A:E52E:827B:3A3D:8800: /* As pseudocode */

2023-11-27T21:15:44Z

As pseudocode

← Previous revision		Revision as of 21:15, 27 November 2023
Line 40:		Line 40:
	append <p,b,c> to ''back''[''l'',''s'',''a'']		append <p,b,c> to ''back''[''l'',''s'',''a'']

	'''if''' ''P''[n,''1'','' s''] is true '''then'''		'''if''' ''P''[n,''1'',''1''] is true '''then'''
	''I'' is member of language		''I'' is member of language
	'''return''' ''back'' -- by ''retracing the steps through back, one can easily construct all possible parse trees of the string.''		'''return''' ''back'' -- by ''retracing the steps through back, one can easily construct all possible parse trees of the string.''

2A00:1028:8396:4C9A:E52E:827B:3A3D:8800: /* As pseudocode */

2023-11-27T21:14:11Z

As pseudocode

← Previous revision		Revision as of 21:14, 27 November 2023
Line 40:		Line 40:
	append <p,b,c> to ''back''[''l'',''s'',''a'']		append <p,b,c> to ''back''[''l'',''s'',''a'']

	'''if''' ''P''[n,''1'',''1''] is true '''then'''		'''if''' ''P''[n,''1'','' s''] is true '''then'''
	''I'' is member of language		''I'' is member of language
	'''return''' ''back'' -- by ''retracing the steps through back, one can easily construct all possible parse trees of the string.''		'''return''' ''back'' -- by ''retracing the steps through back, one can easily construct all possible parse trees of the string.''

SvenSandberg at 20:25, 31 August 2023

2023-08-31T20:25:51Z

← Previous revision		Revision as of 20:25, 31 August 2023
Line 12:		Line 12:
	The standard version of CYK operates only on context-free grammars given in [[Chomsky normal form]] (CNF). However any context-free grammar may be algorithmically transformed into a CNF grammar expressing the same language {{harv\|Sipser\|1997}}.		The standard version of CYK operates only on context-free grammars given in [[Chomsky normal form]] (CNF). However any context-free grammar may be algorithmically transformed into a CNF grammar expressing the same language {{harv\|Sipser\|1997}}.

	The importance of the CYK algorithm stems from its high efficiency in certain situations. Using [[Big O notation\|big ''O'' notation]], the [[Analysis of algorithms\|worst case running time]] of CYK is <math>\mathcal{O}\left( n^3 \cdot \left\| G \right\| \right)</math>, where <math>n</math> is the length of the parsed string and <math>\left\| G \right\|</math> is the size of the CNF grammar <math>G</math> {{harv\|Hopcroft\|Ullman\|1979\|p=140}}. This makes it one of the most efficient parsing algorithms in terms of worst-case [[asymptotic complexity]], although other algorithms exist with better average running time in many practical scenarios.		The importance of the CYK algorithm stems from its high efficiency in certain situations. Using [[Big O notation\|big ''O'' notation]], the [[Analysis of algorithms\|worst case running time]] of CYK is <math>\mathcal{O}\left( n^3 \cdot \left\| G \right\| \right)</math>, where <math>n</math> is the length of the parsed string and <math>\left\| G \right\|</math> is the size of the CNF grammar <math>G</math> {{harv\|Hopcroft\|Ullman\|1979\|p=140}}. This makes it one of the most efficient {{Citation needed\|reason=cubic time does not seem efficient at all; other algorithms claim linear execution time\|date=August 2023}} parsing algorithms in terms of worst-case [[asymptotic complexity]], although other algorithms exist with better average running time in many practical scenarios.

	==Standard form==		==Standard form==

Citation bot: Misc citation tidying. | Use this bot. Report bugs. | #UCB_CommandLine

2023-07-24T23:14:00Z

Misc citation tidying. | Use this bot. Report bugs. | #UCB_CommandLine

← Previous revision		Revision as of 23:14, 24 July 2023
Line 156:		Line 156:
	== Sources ==		== Sources ==
	*{{cite conference \|title= Syntax in universal translation \|last= Sakai \|first= Itiroo \|date= 1962 \|location= London \|publisher= Her Majesty’s Stationery Office \|volume= II \|pages= 593–608 \|conference= 1961 International Conference on Machine Translation of Languages and Applied Language Analysis, Teddington, England}}		*{{cite conference \|title= Syntax in universal translation \|last= Sakai \|first= Itiroo \|date= 1962 \|location= London \|publisher= Her Majesty’s Stationery Office \|volume= II \|pages= 593–608 \|conference= 1961 International Conference on Machine Translation of Languages and Applied Language Analysis, Teddington, England}}
	*{{cite ~~techreport~~ \|last1=Cocke \|first1=John \|author-link1=John Cocke (computer scientist) \|last2=Schwartz \|first2=Jacob T. \|date=April 1970 \|title=Programming languages and their compilers: Preliminary notes \|edition=2nd revised \|publisher=[[Courant Institute of Mathematical Sciences\|CIMS]], [[New York University\|NYU]] \|url=http://www.softwarepreservation.org/projects/FORTRAN/CockeSchwartz_ProgLangCompilers.pdf}}		*{{cite tech report \|last1=Cocke \|first1=John \|author-link1=John Cocke (computer scientist) \|last2=Schwartz \|first2=Jacob T. \|date=April 1970 \|title=Programming languages and their compilers: Preliminary notes \|edition=2nd revised \|publisher=[[Courant Institute of Mathematical Sciences\|CIMS]], [[New York University\|NYU]] \|url=http://www.softwarepreservation.org/projects/FORTRAN/CockeSchwartz_ProgLangCompilers.pdf}}
	* {{cite book \| isbn=0-201-02988-X \| first1=John E. \| last1=Hopcroft \| author1-link=John E. Hopcroft \| first2=Jeffrey D. \| last2=Ullman \| author2-link=Jeffrey D. Ullman \| title=Introduction to Automata Theory, Languages, and Computation \| location=Reading/MA \| publisher=Addison-Wesley \| year=1979 \| url=https://archive.org/details/introductiontoau00hopc }}		* {{cite book \| isbn=0-201-02988-X \| first1=John E. \| last1=Hopcroft \| author1-link=John E. Hopcroft \| first2=Jeffrey D. \| last2=Ullman \| author2-link=Jeffrey D. Ullman \| title=Introduction to Automata Theory, Languages, and Computation \| location=Reading/MA \| publisher=Addison-Wesley \| year=1979 \| url=https://archive.org/details/introductiontoau00hopc }}
	*{{cite ~~techreport~~ \|last1=Kasami \|first1=T. \|author-link1=Tadao Kasami \|year=1965 \|title=An efficient recognition and syntax-analysis algorithm for context-free languages \|number=65-758 \|publisher=[[Air Force Cambridge Research Laboratories\|AFCRL]]}}		*{{cite tech report \|last1=Kasami \|first1=T. \|author-link1=Tadao Kasami \|year=1965 \|title=An efficient recognition and syntax-analysis algorithm for context-free languages \|number=65-758 \|publisher=[[Air Force Cambridge Research Laboratories\|AFCRL]]}}
	*{{cite book \|last1=Knuth \|first1=Donald E. \|author-link1=Donald Knuth \|title=The Art of Computer Programming Volume 2: Seminumerical Algorithms \|publisher=Addison-Wesley Professional \|edition=3rd \|date=November 14, 1997 \|isbn=0-201-89684-2 \|pages=501 }}		*{{cite book \|last1=Knuth \|first1=Donald E. \|author-link1=Donald Knuth \|title=The Art of Computer Programming Volume 2: Seminumerical Algorithms \|publisher=Addison-Wesley Professional \|edition=3rd \|date=November 14, 1997 \|isbn=0-201-89684-2 \|pages=501 }}
	*{{cite journal \|last1=Lang \|first1=Bernard \|title=Recognition can be harder than parsing \|journal=[[Computational Intelligence (journal)\|Comput. Intell.]] \|year=1994 \|volume=10 \|issue=4 \|pages=486–494 \|citeseerx=10.1.1.50.6982 \|doi=10.1111/j.1467-8640.1994.tb00011.x \|s2cid=5873640 }}		*{{cite journal \|last1=Lang \|first1=Bernard \|title=Recognition can be harder than parsing \|journal=[[Computational Intelligence (journal)\|Comput. Intell.]] \|year=1994 \|volume=10 \|issue=4 \|pages=486–494 \|citeseerx=10.1.1.50.6982 \|doi=10.1111/j.1467-8640.1994.tb00011.x \|s2cid=5873640 }}

← Previous revision		Revision as of 23:14, 24 July 2023
Line 156:		Line 156:
	== Sources ==		== Sources ==
	*{{cite conference \|title= Syntax in universal translation \|last= Sakai \|first= Itiroo \|date= 1962 \|location= London \|publisher= Her Majesty’s Stationery Office \|volume= II \|pages= 593–608 \|conference= 1961 International Conference on Machine Translation of Languages and Applied Language Analysis, Teddington, England}}		*{{cite conference \|title= Syntax in universal translation \|last= Sakai \|first= Itiroo \|date= 1962 \|location= London \|publisher= Her Majesty’s Stationery Office \|volume= II \|pages= 593–608 \|conference= 1961 International Conference on Machine Translation of Languages and Applied Language Analysis, Teddington, England}}
	*{{cite ~~techreport~~ \|last1=Cocke \|first1=John \|author-link1=John Cocke (computer scientist) \|last2=Schwartz \|first2=Jacob T. \|date=April 1970 \|title=Programming languages and their compilers: Preliminary notes \|edition=2nd revised \|publisher=[[Courant Institute of Mathematical Sciences\|CIMS]], [[New York University\|NYU]] \|url=http://www.softwarepreservation.org/projects/FORTRAN/CockeSchwartz_ProgLangCompilers.pdf}}		*{{cite tech report \|last1=Cocke \|first1=John \|author-link1=John Cocke (computer scientist) \|last2=Schwartz \|first2=Jacob T. \|date=April 1970 \|title=Programming languages and their compilers: Preliminary notes \|edition=2nd revised \|publisher=[[Courant Institute of Mathematical Sciences\|CIMS]], [[New York University\|NYU]] \|url=http://www.softwarepreservation.org/projects/FORTRAN/CockeSchwartz_ProgLangCompilers.pdf}}
	* {{cite book \| isbn=0-201-02988-X \| first1=John E. \| last1=Hopcroft \| author1-link=John E. Hopcroft \| first2=Jeffrey D. \| last2=Ullman \| author2-link=Jeffrey D. Ullman \| title=Introduction to Automata Theory, Languages, and Computation \| location=Reading/MA \| publisher=Addison-Wesley \| year=1979 \| url=https://archive.org/details/introductiontoau00hopc }}		* {{cite book \| isbn=0-201-02988-X \| first1=John E. \| last1=Hopcroft \| author1-link=John E. Hopcroft \| first2=Jeffrey D. \| last2=Ullman \| author2-link=Jeffrey D. Ullman \| title=Introduction to Automata Theory, Languages, and Computation \| location=Reading/MA \| publisher=Addison-Wesley \| year=1979 \| url=https://archive.org/details/introductiontoau00hopc }}
	*{{cite ~~techreport~~ \|last1=Kasami \|first1=T. \|author-link1=Tadao Kasami \|year=1965 \|title=An efficient recognition and syntax-analysis algorithm for context-free languages \|number=65-758 \|publisher=[[Air Force Cambridge Research Laboratories\|AFCRL]]}}		*{{cite tech report \|last1=Kasami \|first1=T. \|author-link1=Tadao Kasami \|year=1965 \|title=An efficient recognition and syntax-analysis algorithm for context-free languages \|number=65-758 \|publisher=[[Air Force Cambridge Research Laboratories\|AFCRL]]}}
	*{{cite book \|last1=Knuth \|first1=Donald E. \|author-link1=Donald Knuth \|title=The Art of Computer Programming Volume 2: Seminumerical Algorithms \|publisher=Addison-Wesley Professional \|edition=3rd \|date=November 14, 1997 \|isbn=0-201-89684-2 \|pages=501 }}		*{{cite book \|last1=Knuth \|first1=Donald E. \|author-link1=Donald Knuth \|title=The Art of Computer Programming Volume 2: Seminumerical Algorithms \|publisher=Addison-Wesley Professional \|edition=3rd \|date=November 14, 1997 \|isbn=0-201-89684-2 \|pages=501 }}
	*{{cite journal \|last1=Lang \|first1=Bernard \|title=Recognition can be harder than parsing \|journal=[[Computational Intelligence (journal)\|Comput. Intell.]] \|year=1994 \|volume=10 \|issue=4 \|pages=486–494 \|citeseerx=10.1.1.50.6982 \|doi=10.1111/j.1467-8640.1994.tb00011.x \|s2cid=5873640 }}		*{{cite journal \|last1=Lang \|first1=Bernard \|title=Recognition can be harder than parsing \|journal=[[Computational Intelligence (journal)\|Comput. Intell.]] \|year=1994 \|volume=10 \|issue=4 \|pages=486–494 \|citeseerx=10.1.1.50.6982 \|doi=10.1111/j.1467-8640.1994.tb00011.x \|s2cid=5873640 }}