Theory - revision history

Dank at 11:26, 12 March 2025

2025-03-12T11:26:35Z

@@ Line 38: / Line 38: @@
 * Rewrite rule: α→β, where {α, β} are strings of terminals and non-terminals
 * Recognized <i>but not decided</i> by [[Turing Machines]] (ie, any 'yes' answer can be verified, but 'no' cases might not halt)
 [[Category: CS GRE Prep]]

Dank: /* Recursively-Enumerable Languages (Class RE) */

2025-03-12T11:05:02Z

Recursively-Enumerable Languages (Class RE)

← Older revision		Revision as of 11:05, 12 March 2025
Line 37:		Line 37:
	* Type 0 of the [[Chomsky Hierarchy]], and a proper superset of CSLs		* Type 0 of the [[Chomsky Hierarchy]], and a proper superset of CSLs
	* Rewrite rule: α→β, where {α, β} are strings of terminals and non-terminals		* Rewrite rule: α→β, where {α, β} are strings of terminals and non-terminals
	* Recognized ~~*~~but not decided~~*~~ by [[Turing Machines]] (ie, any 'yes' answer can be verified, but 'no' cases might not halt)		* Recognized <i>but not decided</i> by [[Turing Machines]] (ie, any 'yes' answer can be verified, but 'no' cases might not halt)

	[[Category: CS GRE Prep]]		[[Category: CS GRE Prep]]

Dank: /* Recursively-Enumerable Languages (Class RE) */

2025-03-12T11:04:49Z

Recursively-Enumerable Languages (Class RE)

← Older revision		Revision as of 11:04, 12 March 2025
Line 37:		Line 37:
	* Type 0 of the [[Chomsky Hierarchy]], and a proper superset of CSLs		* Type 0 of the [[Chomsky Hierarchy]], and a proper superset of CSLs
	* Rewrite rule: α→β, where {α, β} are strings of terminals and non-terminals		* Rewrite rule: α→β, where {α, β} are strings of terminals and non-terminals
	* Recognized but not decided by [[Turing Machines]] (ie, any 'yes' answer can be verified, but 'no' cases might not halt)		* Recognized *but not decided* by [[Turing Machines]] (ie, any 'yes' answer can be verified, but 'no' cases might not halt)

	[[Category: CS GRE Prep]]		[[Category: CS GRE Prep]]

Dank: /* Formal Languages */

2025-03-12T11:04:37Z

Formal Languages

← Older revision		Revision as of 11:04, 12 March 2025
Line 32:		Line 32:
	* Rewrite rule: αAβ→αγβ, where A is a non-terminal, and {α, β, γ} are strings of terminals and non-terminals		* Rewrite rule: αAβ→αγβ, where A is a non-terminal, and {α, β, γ} are strings of terminals and non-terminals
	* Recognized by linear bounded automata		* Recognized by linear bounded automata
			===Recursive Languages (Class [http://qwiki.stanford.edu/wiki/Complexity_Zoo:R#r R])===
			* Decided by [[Turing Machines]]
	===Recursively-Enumerable Languages (Class [http://qwiki.stanford.edu/wiki/Complexity_Zoo:R#re RE])===		===Recursively-Enumerable Languages (Class [http://qwiki.stanford.edu/wiki/Complexity_Zoo:R#re RE])===
	* Type 0 of the [[Chomsky Hierarchy]], and a proper superset of CSLs		* Type 0 of the [[Chomsky Hierarchy]], and a proper superset of CSLs
	* Rewrite rule: α→β, where {α, β} are strings of terminals and non-terminals		* Rewrite rule: α→β, where {α, β} are strings of terminals and non-terminals
	* Recognized by [[Turing Machines]] (ie, any 'yes' answer can be verified, but 'no' cases might not halt)		* Recognized but not decided by [[Turing Machines]] (ie, any 'yes' answer can be verified, but 'no' cases might not halt)
	~~===Recursive Languages (Class [http://qwiki.stanford.edu/wiki/Complexity_Zoo:R#r R])===~~
	* Decided by [[Turing Machines]]
	[[Category: CS GRE Prep]]		[[Category: CS GRE Prep]]

Dank: /* Regular Languages (Class REG) */

2013-04-04T02:19:10Z

Regular Languages (Class REG)

← Older revision		Revision as of 02:19, 4 April 2013
Line 5:		Line 5:
	* Nondeterminism (NFAs) adds no power to finite state automata (DFAs).		* Nondeterminism (NFAs) adds no power to finite state automata (DFAs).
	* Recognized by finite state machines. Equivalent to [http://qwiki.stanford.edu/wiki/Complexity_Zoo:D#dspace DSPACE(1)].		* Recognized by finite state machines. Equivalent to [http://qwiki.stanford.edu/wiki/Complexity_Zoo:D#dspace DSPACE(1)].
	* Closed under union, concatenation, Kleene, intersection, difference, complement, reverse, right-quotient, homomorphism		* Closed under union, concatenation, Kleene, intersection, difference, complement, reverse, right-quotient, homomorphism, derivation
			** Derivation with respect to '''L''' and a: all the strings in L starting with 'a' have it removed
	* Pumping lemma: A language '''L''' is regular if and only if there exists a positive integer ''m'' such that for any ''w'' ∈ '''L''' with \|''w''\| ≥ ''m'' there exist strings ''x'', ''y'' and ''z'' such that:		* Pumping lemma: A language '''L''' is regular if and only if there exists a positive integer ''m'' such that for any ''w'' ∈ '''L''' with \|''w''\| ≥ ''m'' there exist strings ''x'', ''y'' and ''z'' such that:
	** ''w'' = ''xyz'',		** ''w'' = ''xyz'',
Line 11:		Line 12:
	** \|''y''\| ≥ 1, and		** \|''y''\| ≥ 1, and
	** ''xy<sup>i</sup>z'' ∈ '''L''' for all ''i'' ≥ 0		** ''xy<sup>i</sup>z'' ∈ '''L''' for all ''i'' ≥ 0

	===Context-Free Languages (CFLs) / Grammars (CFGs)===		===Context-Free Languages (CFLs) / Grammars (CFGs)===
	* Type 2 of the [[Chomsky Hierarchy]], and a proper superset of RLs		* Type 2 of the [[Chomsky Hierarchy]], and a proper superset of RLs

Dank: /* Efficiently-Parsed CFLs */

2009-10-10T03:00:57Z

Efficiently-Parsed CFLs

← Older revision		Revision as of 03:00, 10 October 2009
Line 20:		Line 20:
	* The intersection of an RL and CFL is a CFL, but CFLs are not closed under intersection		* The intersection of an RL and CFL is a CFL, but CFLs are not closed under intersection
	* Universality, language equality, language inclusion, and regularity are all undecidable given arbitrary input CFLs		* Universality, language equality, language inclusion, and regularity are all undecidable given arbitrary input CFLs
	====Efficiently-Parsed CFLs====		====Efficiently-Parsed CFLs (using ''n'' tokens of lookahead)====
	* LL(''n'') (Lewis and Stearns, 1968):		* LL(''n'') (Lewis and Stearns, 1968):
	** Language equality is decidable for the ''simple grammars'', a subset of LL(1)		** Language equality is decidable for the ''simple grammars'', a subset of LL(1)
	* LR(''n'') (Knuth, 1965):		* LR(''n'') (Knuth, 1965):
	* LALR(''n''):		* LALR(''n''):

	===Context-Sensitive Languages===		===Context-Sensitive Languages===
	* Type 1 of the [[Chomsky Hierarchy]], and a proper superset of CFLs		* Type 1 of the [[Chomsky Hierarchy]], and a proper superset of CFLs

Dank: /* Formal Languages */

2009-10-09T23:09:13Z

Formal Languages

← Older revision		Revision as of 23:09, 9 October 2009
Line 19:		Line 19:
	* Not closed under complement or difference		* Not closed under complement or difference
	* The intersection of an RL and CFL is a CFL, but CFLs are not closed under intersection		* The intersection of an RL and CFL is a CFL, but CFLs are not closed under intersection
	* Universality, language equality, language inclusion, and regularity are all undecidable given input CFLs		* Universality, language equality, language inclusion, and regularity are all undecidable given arbitrary input CFLs
	====Efficiently-Parsed CFLs====		====Efficiently-Parsed CFLs====
	* LL(''n'') (Lewis and Stearns, 1968):		* LL(''n'') (Lewis and Stearns, 1968):

Dank: /* Formal Languages */

2009-10-09T23:08:44Z

Formal Languages

← Older revision		Revision as of 23:08, 9 October 2009
Line 11:		Line 11:
	** \|''y''\| ≥ 1, and		** \|''y''\| ≥ 1, and
	** ''xy<sup>i</sup>z'' ∈ '''L''' for all ''i'' ≥ 0		** ''xy<sup>i</sup>z'' ∈ '''L''' for all ''i'' ≥ 0

	===Context-Free Languages (CFLs) / Grammars (CFGs)===		===Context-Free Languages (CFLs) / Grammars (CFGs)===
	* Type 2 of the [[Chomsky Hierarchy]], and a proper superset of RLs		* Type 2 of the [[Chomsky Hierarchy]], and a proper superset of RLs
Line 21:		Line 20:
	* The intersection of an RL and CFL is a CFL, but CFLs are not closed under intersection		* The intersection of an RL and CFL is a CFL, but CFLs are not closed under intersection
	* Universality, language equality, language inclusion, and regularity are all undecidable given input CFLs		* Universality, language equality, language inclusion, and regularity are all undecidable given input CFLs

	====Efficiently-Parsed CFLs====		====Efficiently-Parsed CFLs====
	* LL(''n'') (Lewis and Stearns, 1968):		* LL(''n'') (Lewis and Stearns, 1968):
Line 27:		Line 25:
	* LR(''n'') (Knuth, 1965):		* LR(''n'') (Knuth, 1965):
	* LALR(''n''):		* LALR(''n''):


	===Context-Sensitive Languages===		===Context-Sensitive Languages===
	* Type 1 of the [[Chomsky Hierarchy]], and a proper superset of CFLs		* Type 1 of the [[Chomsky Hierarchy]], and a proper superset of CFLs
Line 37:		Line 33:
	* Rewrite rule: α→β, where {α, β} are strings of terminals and non-terminals		* Rewrite rule: α→β, where {α, β} are strings of terminals and non-terminals
	* Recognized by [[Turing Machines]] (ie, any 'yes' answer can be verified, but 'no' cases might not halt)		* Recognized by [[Turing Machines]] (ie, any 'yes' answer can be verified, but 'no' cases might not halt)

	===Recursive Languages (Class [http://qwiki.stanford.edu/wiki/Complexity_Zoo:R#r R])===		===Recursive Languages (Class [http://qwiki.stanford.edu/wiki/Complexity_Zoo:R#r R])===
	* Decided by [[Turing Machines]]		* Decided by [[Turing Machines]]
	[[Category: CS GRE Prep]]		[[Category: CS GRE Prep]]

Dank: /* Formal Languages */

2009-10-09T23:08:29Z

Formal Languages

← Older revision		Revision as of 23:08, 9 October 2009
Line 24:		Line 24:
	====Efficiently-Parsed CFLs====		====Efficiently-Parsed CFLs====
	* LL(''n'') (Lewis and Stearns, 1968):		* LL(''n'') (Lewis and Stearns, 1968):
			** Language equality is decidable for the ''simple grammars'', a subset of LL(1)
	* LR(''n'') (Knuth, 1965):		* LR(''n'') (Knuth, 1965):
			* LALR(''n''):


	===Context-Sensitive Languages===		===Context-Sensitive Languages===

Dank at 23:05, 9 October 2009

2009-10-09T23:05:55Z

← Older revision		Revision as of 23:05, 9 October 2009
Line 20:		Line 20:
	* Not closed under complement or difference		* Not closed under complement or difference
	* The intersection of an RL and CFL is a CFL, but CFLs are not closed under intersection		* The intersection of an RL and CFL is a CFL, but CFLs are not closed under intersection
			* Universality, language equality, language inclusion, and regularity are all undecidable given input CFLs

	====Efficiently-Parsed CFLs====		====Efficiently-Parsed CFLs====
	* LL(''n'') (Lewis and Stearns, 1968):		* LL(''n'') (Lewis and Stearns, 1968):
Line 35:		Line 37:
	===Recursive Languages (Class [http://qwiki.stanford.edu/wiki/Complexity_Zoo:R#r R])===		===Recursive Languages (Class [http://qwiki.stanford.edu/wiki/Complexity_Zoo:R#r R])===
	* Decided by [[Turing Machines]]		* Decided by [[Turing Machines]]

	[[Category: CS GRE Prep]]		[[Category: CS GRE Prep]]