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]