regular_language (988B)
1 # Regular language 2 3 ## [computational_problem] 4 5 - [regular_language_membership] 6 - [approximate_membership] 7 - [dynamic_membership] 8 - [sliding_window] 9 - [regular_language_communication_complexity] 10 11 ## [regular_language_list] 12 13 - [parity] 14 15 ## [regular_language_family] 16 17 - [locally_testable_language] 18 - [regular_language_sparse]: polynomial number of words per length 19 - [regular_language_slender]: constant number of words 20 - [regular_language_thin]: at most one word 21 22 ## Connections 23 24 - [regular_language_communication_complexity] 25 26 ## Generalizations 27 28 - [regular_tree_language] 29 30 ## Concepts 31 32 - [star_height] 33 - arbitrarily large 34 - connection to [cycle_rank] of [automata] via [eggans_theorem] 35 - [generalized_star_height] en ajoutant [complementation] 36 - generalized star height of zero is [star_free_language] 37 38 ## Results 39 40 - [myhill_nerode_theorem] 41 - [myhill_nerode_relation] 42 - [pumping_lemma] 43 44 See also: [automata] 45 46 Up: [formal_language], [regular] 47 48 Aliases: regular languages