index
:
teach/inf105.git
master
THL (théorie des langages)
git repository hosting
summary
refs
log
tree
commit
diff
stats
log msg
author
committer
range
path:
root
/
notesinf105.tex
Commit message (
Collapse
)
Author
Age
Files
Lines
*
Two typos (thanks, Pierre Pébereau).
David A. Madore
20200123
1
2
/
+2

*
Add two exercises from last year's exam (plus, update index very slightly).
printed2019
David A. Madore
20191022
1
2
/
+294

*
Minor clarifications about computability and universality.
David A. Madore
20190116
1
27
/
+38

*
Fix bijection between ℕ² and ℕ.
David A. Madore
20190116
1
3
/
+3

*
Various improvements to index.
David A. Madore
20190107
1
25
/
+31

*
Copy a lot of exercises into the course notes.
printed2018
David A. Madore
20181003
1
2
/
+2586

*
Small syntactic clarifications.
David A. Madore
20180116
1
7
/
+7

*
Take into account Antoine's remarks.
David A. Madore
20180115
1
3
/
+3

*
Try to make clarification even clearer.
David A. Madore
20180108
1
2
/
+2

*
Spellcheck.
David A. Madore
20180108
1
2
/
+2

*
Take into account Antoine's remarks.
David A. Madore
20180108
1
10
/
+13

*
Fix proof of standardization of automata.
David A. Madore
20171128
1
3
/
+6





The case where the added state should have been final was missing. Thanks to Antoine for pointing this out.
*
Fix typo pointed out by Mikaël.
David A. Madore
20171127
1
1
/
+1

*
Minor clarification.
David A. Madore
20171120
1
1
/
+1

*
Increase inner margin (at expense of outer margin, so as to keep line width).
printed2017
David A. Madore
20171114
1
1
/
+1

*
Plenty more typos (thanks, Hélène S.).
David A. Madore
20171114
1
11
/
+11

*
Imprimatur.
David A. Madore
20171113
1
10
/
+7

*
Corrections suggested by a3nm.
David A. Madore
20171113
1
3
/
+3

*
Typo.
David A. Madore
20171111
1
1
/
+1

*
Missing comma.
David A. Madore
20171110
1
1
/
+1

*
Corrections suggested by Mikaël.
David A. Madore
20171110
1
79
/
+83

*
Downgrade level of unfinishedness and associated warning.
David A. Madore
20171108
1
9
/
+6

*
Add remark about escaping regexps under Unix shell.
David A. Madore
20171108
1
0
/
+8

*
Add remark about Kleene's star as smallest solution to an equation.
David A. Madore
20171108
1
0
/
+10

*
Change notation A_r to A(r) for consistency's sake.
David A. Madore
20171108
1
17
/
+20

*
Add more white space to make text less dense.
David A. Madore
20171108
1
34
/
+260

*
Add footnote on grammar of regexps themselves.
David A. Madore
20171108
1
2
/
+9

*
Change notations L_r and L_A to L(r) and L(A).
David A. Madore
20171108
1
52
/
+53

*
Corrections suggested by Jacques.
David A. Madore
20171107
1
8
/
+8

*
Expand discussion about practical parsing of CFGs (LL and LR approaches).
David A. Madore
20171107
1
45
/
+97

*
Reread description of CYK algorithm.
David A. Madore
20171106
1
14
/
+15

*
A brief description of the CYK dynamic programming algorithm for CFGs.
David A. Madore
20171106
1
8
/
+107

*
Reread and rework introduction to computability.
David A. Madore
20171103
1
125
/
+184

*
Reread section on formal grammars. Rewrite proof that algebraic languages ↵
David A. Madore
20171103
1
51
/
+131




are decidable.
*
More clarifications.
David A. Madore
20171102
1
13
/
+20

*
Various clarifications on contextfree grammars.
David A. Madore
20171102
1
97
/
+146

*
Typographic logic.
David A. Madore
20171102
1
6
/
+6

*
Clarify what \footnotesize means.
David A. Madore
20171102
1
0
/
+5

*
Minor clarifications on formal grammars.
David A. Madore
20171101
1
3
/
+11

*
Some remarks on degenerate cases.
David A. Madore
20171101
1
2
/
+27

*
Primary terminology is "minimal" automaton, not "canonical".
David A. Madore
20171101
1
5
/
+5

*
Change acronym for incomplete automata to "DFAi" with lowercase i.
David A. Madore
20171101
1
36
/
+36




Is this really a good idea? Maybe not.
*
Rework various comments (especially on regular expressions).
David A. Madore
20171101
1
68
/
+107

*
Add another example of state elimination (limiteddepth balanced parentheses).
David A. Madore
20171101
1
0
/
+63

*
An intuitive explanation of the pumping lemma's uses.
David A. Madore
20171101
1
0
/
+12

*
Reread sections on recognizable languages: various updates, clarifications, ↵
David A. Madore
20171031
1
49
/
+86




fixes.
*
Add general intro blurb.
David A. Madore
20171031
1
7
/
+64

*
Reread sections on automata: various updates, clarifications, fixes.
David A. Madore
20171030
1
118
/
+151

*
Compatibility with older TeXlive.
David A. Madore
20171030
1
0
/
+1

*
Introduction and clarifications on contextfree grammars.
David A. Madore
20171030
1
17
/
+82

[next]