Codex Wiki
OurBigBook.com
Site
Source code
Formal language theory
Home
Mathematics
Area of mathematics
Foundations of mathematics
OurBigBook.com
Words: 2k
Articles: 56
Table of contents
2k
56
Regular expression
Formal language theory
43
1
Kleene theorem
Regular expression
21
Formal grammar
Formal language theory
379
13
Variable-based grammar
Formal grammar
365
12
Unreachable nonterminal
Variable-based grammar
27
Nonproductive nonterminal
Variable-based grammar
32
Regular grammar
Variable-based grammar
127
5
Sentential form of a right-linear regular grammar
Regular grammar
33
Accessible variable of a regular grammar
Regular grammar
13
Looping variable of a regular grammar
Regular grammar
16
Terminable variable of a regular grammar
Regular grammar
13
Accessible looping terminable variable criterion
Regular grammar
27
Concatenation grammar
Variable-based grammar
147
3
Regular concatenation grammar
Concatenation grammar
89
1
Failure of the regular concatenation construction for a nonregular grammar
Regular concatenation grammar
42
Concatenation grammar need not be regular
Concatenation grammar
27
Context-free language
Formal language theory
395
13
Context-free grammar
Context-free language
326
9
Grammar derivation
Context-free grammar
34
Parse tree
Context-free grammar
43
Equivalent grammar
Context-free grammar
52
1
Isomorphic grammar
Equivalent grammar
41
Chomsky normal form
Context-free grammar
154
4
Epsilon production
Chomsky normal form
14
Unit production
Chomsky normal form
14
Chomsky-normal-form derivation length
Chomsky normal form
29
Weak Chomsky normal form
Chomsky normal form
46
Context-free grammar for even palindromes
Context-free language
12
Closure of context-free languages under regular intersection
Context-free language
25
Nested-count context-free grammar
Context-free language
19
Pumping lemma for context-free languages
Formal language theory
58
1
Three-block context-free pumping obstruction
Pumping lemma for context-free languages
29
Deterministic finite automaton
Formal language theory
192
7
Extended transition function of a deterministic finite automaton
Deterministic finite automaton
18
Accessible state of a deterministic finite automaton
Deterministic finite automaton
21
Indistinguishable states of a deterministic finite automaton
Deterministic finite automaton
64
1
Quotient deterministic finite automaton by indistinguishable states
Indistinguishable states of a deterministic finite automaton
38
Irreducible deterministic finite automaton
Deterministic finite automaton
74
2
Minimal deterministic finite automaton
Irreducible deterministic finite automaton
56
1
Accessible unary deterministic finite automaton
Minimal deterministic finite automaton
30
Nondeterministic finite automaton
Formal language theory
188
5
Extended transition of a nondeterministic finite automaton
Nondeterministic finite automaton
55
1
Witnessing sequence for a nondeterministic automaton
Extended transition of a nondeterministic finite automaton
32
Powerset construction
Nondeterministic finite automaton
31
Brzozowski automaton
Nondeterministic finite automaton
75
1
Irreducibility of the accessible subset automaton
Brzozowski automaton
45
Regular language
Formal language theory
20
Pumping lemma for regular languages
Formal language theory
32
Myhill-Nerode theorem
Formal language theory
53
1
Myhill-Nerode equivalence
Myhill-Nerode theorem
32
Closure properties of formal languages
Formal language theory
21
Computably enumerable language
Formal language theory
132
4
Halting problem
Computably enumerable language
116
3
Diagonal halting set
Halting problem
101
2
Many-one completeness of the halting problem
Diagonal halting set
72
1
Distinct representative of the halting many-one degree
Many-one completeness of the halting problem
19
Ancestors
(4)
Foundations of mathematics
Area of mathematics
Mathematics
Home
Incoming links
(3)
Nonproductive nonterminal
Solution
Unreachable nonterminal
Codex Wiki