Title: Theory / Unimportant / CS / Fundamental / Automata / TATA / 2 Grammars and expressions
Tags: examplesSwitchExample1 hasSeenConjDef toBinaryRelation

Name: A tree grammar
Definition: \(N\) a set of non-terminal
Page: 51
Chapter: 2
Section: 1.1
Definition2: \(S\in N\) an axiom
Conjdef: A tuple
Definition3: \(\mathcal F\) a set of terminal symbols disjoint from \(N\)
Definition4: \(R\) a set of production rules

Name: A production rule
Definition: An element of the form \(\alpha_1\to\alpha_2\) with \(\alpha_i\) are trees of \(T(\mathcal F\cup N\cup\mathcal X)\), \(\alpha_i\) contains at least one non-terminal and \(\mathcal X\) a set of dummy variables.
Page: 51
Chapter: 2
Section: 1.1
Variables: \(N\) a set of non-terminal
\(\mathcal F\) a set of terminal symbols

Name: A regular tree grammar
Definition: each non-terminal have arity 0
Page: 51
Chapter: 2
Section: 1.1
Definition2: each rules are of the form \(A\to\alpha\) with \(A\in N\) and \(\alpha\in T(\mathcal F\cup N)\)
Example: List → nil
List → cons(N at, List)
Nat → 0
Nat → s(N at)
Conjdef: A tree gramar \((S,N,\mathcal F,R)\) such that

Page: 51
Definition: The relation containing \((s,t)\) such that there exists a context \(C\) such that \(s=C[\alpha_1(\vec x)]\) and \(t=C[\alpha_2(\vec x)]\) and \((\alpha_1,\alpha_2)\in R\)
Chapter: 2
Section: 1.1
Variables: \(G=(S,N,\mathcal F,R)\) a tree grammar
Notation: \(\to_G\)

Name: The language generated by \(G\)
Definition: The set of terms of \(T(\mathcal F)\) which can be reached by successive derivations starting from the axiom.
Page: 51
Chapter: 2
Section: 1.1
Variables: \(G=(S,N,\mathcal F,R)\) a tree grammar
Notation: \(L(G)\)

Name: A regular tree language
Definition: A language generated by a regular tree grammar.
Page: 51
Chapter: 2
Section: 1.1

Name: Equivalent grammars
Definition: Grammars generating the same language.
Page: 52
Chapter: 2
Section: 1.1

Name: A reachable non-terminal
Definition: A non-terminal such that there is a derivation from the axiom containing this non-terminal.
Page: 52
Chapter: 2
Section: 1.1
Variables: \(G=(S,N,\mathcal F,R)\) a tree grammar

Name: A productive non-terminal
Definition: A non-terminal \(A\) such that \(L_G(A)\) is non-empty
Page: 52
Chapter: 2
Section: 1.1
Variables: \(G=(S,N,\mathcal F,R)\) a tree grammar

Definition: \(L(A,N,\mathcal F,R)\)
Page: 51
Chapter: 2
Section: 1.1
Variables: \(G=(S,N,\mathcal F,R)\) a tree grammar
Notation: \(L_G(A)\)

Name: A reduced tree grammar
Definition: A tree grammar whose every non-terminals are reachable and productive.
Page: 52
Chapter: 2
Section: 1.1

Smaller0: \(G\) is regular
Greater0: \(G\) is equivalent to a reduced normalized regular tree grammar
Page: 53
Chapter: 2
Section: 1.1
Variables: \(G=(S,N,\mathcal F,R)\) a tree grammar
Index: , 14
Kind: , prop

Name: A normalized regular tree grammar
Definition: A tree grammar whose production rules are of the form \(A\to f(A_1,\dots,A_n)\)
Page: 53
Chapter: 2
Section: 1.1