Revision #90 → #1115 · back to history
addedContext-free grammar28d3e7801ece
addedFormal grammar287f76bbe6cc
addedLanguage generated by a grammar52f2520b617c
addedContext-free languagecc152e598c76
addedLanguage equality undecidable0e1c84ef9209
addedCFG as 4-tuple1bebec028483
addedNonterminal / variablede2b01cb52d9
addedTerminalsdf174e215d3b
addedProduction rulesdfbb12d6f9a5
addedStart variable1f3d497724b4
addedProduction rule as pairb4b8f0628534
addedε-production9c45aa67dde2
addedAlternatives4ef8af31e9d9
addedDirectly yieldsac42bd1ca268
addedYields / derived0976406a598d
addedLanguage of a grammar00f00ccf5fbf
addedContext-free language (CFL)fdf4299b0733
addedPushdown automata recognize CFLs2d0a48b991fe
addedWords with reverse grammar891ff5899a5b
addedPalindrome grammardf4a43993e96
addedWell-formed parentheses5a0e816e18eb
addedNested parentheses and bracketsbd8493a06e6d
addedMatching pairs a^n b^n (n≥1)f469c6c11961
addedMatching pairs a^n b^n (n≥0)2eb98ae46efd
addedUnequal number of as and bs33b3536abc41
addedSecond block of bs double sizeee1d5ea9abbd
addedFirst-order logic formulas7c6e1a7c7447
addedTwo-type balanced parentheses not CF72baeadeba71
addedRegular grammars are context-free20c92c5050be
addedRegular context-free grammard046bb8dfcac
addedRegular grammar to NFA315a52bf16d7
addedDerivationda853296eb5a
addedLeftmost / rightmost derivation7f43809e81f0
addedParse treed1c91d11fb2a
addedAmbiguous grammar13f3da710f5f
addedInherently ambiguous language54004d28826b
addedEquivalent normal forms exist6698dbb07eb9
addedCYK polynomial-time decision19dba8ba5cba
addedClosure under operations28c99c25a228
addedNon-closure under intersection6bbe92389d15
addedParsing is decidable2330173f26d2
addedValiant: parsing via matrix multiplication76b966d42373
addedLee: lower bound for CFG parsing643c2f7c1d5f
addedProductive symbol66a0bd7ed55d
addedReachable symbolaaf4b0d336d2
addedUseless symbolfe7a11898923
addedNullable symboleaa5108aa519
addedElimination algorithmsd74c845a3cd4
addedProper grammarffab14ff812e
addedTransform to proper grammar85e700c714ab
addedRegularity / LL(k) checks decidableb14648204f65
addedLanguage regularity undecidabled2288c6a02fd
addedEmptiness and finiteness decidable3be7c5da175c
addedEmptiness decidable for CFGs453b9e8dd98a
addedUniversality undecidable283ce7f9d41f
addedLanguage equality undecidable9e4e9f40dc4b
addedLanguage inclusion undecidablee1294158d4f6
addedChomsky hierarchy level undecidable0c7ae92acaac
addedGrammar ambiguity undecidable13ddb7ca34b1
addedLanguage disjointness undecidable9c0f7409508d
addedExtended context-free grammard85a58ae7664
addedExtended CFGs describe CFLs330ab1dafe49
addedContext-sensitive grammarscc982c4e77e6
addedLR(k) grammars3fed0cc2c805
addedLL(k) grammars2466dee9c270
addedSimple grammars9ef0ade53553
addedBracketed grammars987af91ab292
addedLinear grammars8f38752d91eb
addedRegular grammars subclass21a1297dc1e1