wiki_research

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

formal_language_theory (1104B)


      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 
     36 ## Other notions
     37 
     38 - [word_equation]
     39 - [sliding_window]
     40 - [atom]
     41 - [parikh_automaton], [parikh_image]
     42 - [formal_language_separation]
     43 - [determinism_language]
     44 - [unambiguity]
     45 
     46 ## Results
     47 
     48 - [higmans_lemma]
     49 - [krohn_rhodes]
     50 - [brzozoswki_mccluksey]
     51 - [language_power_series]: connections between formal languages and [power_series]
     52 - [pumping_lemma]
     53 - [ogdens_lemma]
     54 - [interchange_lemma] https://en.wikipedia.org/wiki/Interchange_lemma
     55   - other such results: https://cstheory.stackexchange.com/a/54032
     56 
     57 Up: [theoretical_computer_science]
     58 
     59 See also: [word_combinatorics]