wiki_research

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

formal_language_theory (1081B)

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