wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

formal_language_theory (1154B)

      1 # Formal language theory
      2 
      3 Studies [formal_languages]
      4 
      5 ## Concepts
      6 
      7 - [alphabet]
      8 - [word]
      9   - [empty_word]
     10 - [formal_language]
     11 - [prefix], [suffix], [subword], [subsequence]
     12 - [chomsky_hierarchy]
     13 
     14 ## Operations
     15 
     16 - [shuffle]
     17 
     18 ## Languages
     19 
     20 - [regular_language]
     21   - [piecewise_testable_language]
     22   - [locally_testable_language]
     23 - [regular_expression]
     24 - [automata]
     25 - [transducer]
     26   - [tree_automaton]
     27     - [tree_walking_automaton]
     28 - [context_free_grammar]
     29   - [pcfg]
     30   - [grammar_variants]
     31 
     32 ## Problems
     33 
     34 - [constrained_topological_sort]
     35 - [star_height_problem]
     36 
     37 ## Other notions
     38 
     39 - [word_equation]
     40 - [sliding_window]
     41 - [atom]
     42 - [parikh_automaton], [parikh_image]
     43 - [formal_language_separation]
     44 - [determinism_language]
     45 - [unambiguity]
     46 
     47 ## Results
     48 
     49 - [higmans_lemma]
     50 - [krohn_rhodes]
     51 - [brzozoswki_mccluksey]
     52 - [language_power_series]: connections between formal languages and [power_series]
     53 - [pumping_lemma]
     54 - [ogdens_lemma]
     55 - [interchange_lemma] https://en.wikipedia.org/wiki/Interchange_lemma
     56   - other such results: https://cstheory.stackexchange.com/a/54032
     57 - [myhill_nerode_theorem]
     58 
     59 Up: [theoretical_computer_science]
     60 
     61 See also: [word_combinatorics]