Formula appendix (Docling inventory)
This page lists formula-related content extracted from Docling markdown in the markdown_library workspace. Rendered blocks use the same $ / $$ conventions as Math rendering rules (KaTeX on this site; equivalent LaTeX typically works in MathJax).
Pipeline status
- Enriched Docling run: a sample PDF was converted with
--enrich-formula(seemarkdown_library/pdfs/andautomata/docling_md_formula_runs/). Drop additional licensed PDFs intopdfs/and runscripts/formula_extraction/run_docling_enriched.py. - Legacy exports: many entries are
<!-- formula-not-decoded -->placeholders from earlier conversions without--enrich-formula. Those entries show context in plain text; the rendered cell uses\text{...}as a stand-in until OCR LaTeX is available.
Inventory summary
| Metric | Value |
|---|---|
| Generated (UTC) | 2026-04-19T07:44:22.220335+00:00 |
| Total records | 983 |
LaTeX-like $...$ / $$...$$ in markdown |
0 |
| Formula placeholders | 983 |
| Shown below | 0 LaTeX extracts + 983 placeholder contexts (capped) |
Full machine-readable inventory: assets/formula_inventory.json (or the copy committed alongside this site).
Entries (collapsible)
Placeholder regions (formula-not-decoded)
1. ph-81f2c804f2fbd226c057 — agents/docling_md/Agents in Trustworthy.md
### Plain (markdown context)
m .' 'Who did __?' ``` ``` (5.51) [' VP Imperative.' 'I don't want to __.'] ' Get going .' 'I don't want to __.' (5.52) ['I see .' 'No, you don't __.'] 'I see .' 'No, you don't __.' ``` Although these constructions are presented as text strings for clarity's sake, they are actually recorded and pro cessed in terms of meaning repre senta tions, which allows for both lexical variability (paraphrasing) and the potential for intervening material, as in (5.53). Another kind of VP ellipsis that is handled during Extended Semantics is what we call repetition structures ,…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{m .' 'Who did \_\_?' ``` ``` (5.51) [' VP Imperative.' 'I don't want to \_\_.'] ' Get going .' 'I don't want to \_\_.' (5.52) ['I see .' 'No, you don't \_\_.'] 'I see .' 'No, you don't \_\_.' ``` Although these constructions are presented as text strings for clarity's sake, they are actua…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 2. ph-be94782a0ed3a41ed509 — agents/docling_md/Agents in Trustworthy_chapters/Agents in Trustworthy_chapter_2.5.md
### Plain (markdown context)
m .' 'Who did __?' ``` ``` (5.51) [' VP Imperative.' 'I don't want to __.'] ' Get going .' 'I don't want to __.' (5.52) ['I see .' 'No, you don't __.'] 'I see .' 'No, you don't __.' ``` Although these constructions are presented as text strings for clarity's sake, they are actually recorded and pro cessed in terms of meaning repre senta tions, which allows for both lexical variability (paraphrasing) and the potential for intervening material, as in (5.53). Another kind of VP ellipsis that is handled during Extended Semantics is what we call repetition structures ,…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{m .' 'Who did \_\_?' ``` ``` (5.51) [' VP Imperative.' 'I don't want to \_\_.'] ' Get going .' 'I don't want to \_\_.' (5.52) ['I see .' 'No, you don't \_\_.'] 'I see .' 'No, you don't \_\_.' ``` Although these constructions are presented as text strings for clarity's sake, they are actua…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 3. ph-cc2293253ed9e4052084 — agents/docling_md/PromptEngineeringForDeveloper.md
### Plain (markdown context)
stant", "content": "When Harry was 25 yea \ rs old, his sister was 29 years old. There's 4 year differences between them and the sister is older than Harry. When Harry is 30 years old, h is sister should be 34 years old."}, {"role": "user", "content": f" { message } "}, ], temperature=1, max_tokens=256, top_p=1, frequency_penalty=0, presence_penalty=0 ) try : print("Felix:", response.choices[0].message.content) except : print("Felix: Sorry, a problem occurred. Please try again l \ ``` ater.") ## When asked the following question, the answer was correct: Felix : Hi…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{stant", "content": "When Harry was 25 yea \textbackslash rs old, his sister was 29 years old. There's 4 year differences between them and the sister is older than Harry. When Harry is 30 years old, h is sister should be 34 years old."\}, \{"role": "user", "content": f" \{ message \} "\}, ], tempe…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 4. ph-72962440b734fbdfbbc9 — agents/docling_md/PromptEngineeringForDeveloper.md
### Plain (markdown context)
's not very 'surprised' by the actual next word because it expected it. Conversely, if it struggles to predict the next word, its perplexity is high - it's more 'surprised' by the actual word that comes next. Think of this as giving someone a task in a language they are fluent in versus a language they've just started learning. Naturally, they'd perform better with the familiar language. ## 12.2 - How to Calculate Perplexity? In general, perplexity is calculated using the following formula: Where: - s is the sample - wx is a word from the sample - N is the number …
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{'s not very 'surprised' by the actual next word because it expected it. Conversely, if it struggles to predict the next word, its perplexity is high - it's more 'surprised' by the actual word that comes next. Think of this as giving someone a task in a language they are fluent i…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 5. ph-258a141e459e78681212 — agents/docling_md/PromptEngineeringForDeveloper_chapters/PromptEngineeringForDeveloper_chapter_1.6.md
### Plain (markdown context)
stant", "content": "When Harry was 25 yea \ rs old, his sister was 29 years old. There's 4 year differences between them and the sister is older than Harry. When Harry is 30 years old, h is sister should be 34 years old."}, {"role": "user", "content": f" { message } "}, ], temperature=1, max_tokens=256, top_p=1, frequency_penalty=0, presence_penalty=0 ) try : print("Felix:", response.choices[0].message.content) except : print("Felix: Sorry, a problem occurred. Please try again l \ ``` ater.") ## When asked the following question, the answer was correct: Felix : Hi…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{stant", "content": "When Harry was 25 yea \textbackslash rs old, his sister was 29 years old. There's 4 year differences between them and the sister is older than Harry. When Harry is 30 years old, h is sister should be 34 years old."\}, \{"role": "user", "content": f" \{ message \} "\}, ], tempe…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 6. ph-86eefa320d188eb79d8c — agents/docling_md/PromptEngineeringForDeveloper_chapters/PromptEngineeringForDeveloper_chapter_1.6.md
### Plain (markdown context)
's not very 'surprised' by the actual next word because it expected it. Conversely, if it struggles to predict the next word, its perplexity is high - it's more 'surprised' by the actual word that comes next. Think of this as giving someone a task in a language they are fluent in versus a language they've just started learning. Naturally, they'd perform better with the familiar language. ## 12.2 - How to Calculate Perplexity? In general, perplexity is calculated using the following formula: Where: - s is the sample - wx is a word from the sample - N is the number …
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{'s not very 'surprised' by the actual next word because it expected it. Conversely, if it struggles to predict the next word, its perplexity is high - it's more 'surprised' by the actual word that comes next. Think of this as giving someone a task in a language they are fluent i…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 7. ph-4f053d7443ccb1797caa — automata/docling_md/AWK-implementation.md
### Plain (markdown context)
he nodes with 2 or more possible next nodes will be of type 2. This can lead to significant memory waste for a node. For example, if a node has only six possible next nodes, the type 2 node will have 250 NULL pointers in its array. In this work, we compare different trie configurations using (1), where P is the performance, C is the number of clock cycles per character and M is the overall memory used. This relation allows to find the best compromise between C and M . ## 3. Methods To compare various trie configurations, we used a virtual machine with Xubuntu 14.0…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{he nodes with 2 or more possible next nodes will be of type 2. This can lead to significant memory waste for a node. For example, if a node has only six possible next nodes, the type 2 node will have 250 NULL pointers in its array. In this work, we compare different trie configu…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 8. ph-f8231af044f65f20f782 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
s is the set of all strings of symbols in a given alphabet. Definition 1.8 Let A be a set. A ′ = U -A is the set of all elements not in A. Example 1.3 Let A be the set of even integers and U be the set of integers. Then A ′ is the set of odd integers. Example 1.4 Let A = { x : x collects coins } , then A ′ = { x : x does not collect coins } . The proof of the following theorem is left to the reader. Theorem 1.1 Let A, B, and C be subsets of the universal set U (a) Distributive properties - (b) Idempotent properties - (d) De Morgan's la…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{s is the set of all strings of symbols in a given alphabet. Definition 1.8 Let A be a set. A ′ = U -A is the set of all elements not in A. Example 1.3 Let A be the set of even integers and U be the set of integers. Then A ′ is the set of odd integers. Example 1.4 Let A = \{ x : x…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 9. ph-dee9d9d636688b57be58 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
symbols in a given alphabet. Definition 1.8 Let A be a set. A ′ = U -A is the set of all elements not in A. Example 1.3 Let A be the set of even integers and U be the set of integers. Then A ′ is the set of odd integers. Example 1.4 Let A = { x : x collects coins } , then A ′ = { x : x does not collect coins } . The proof of the following theorem is left to the reader. Theorem 1.1 Let A, B, and C be subsets of the universal set U (a) Distributive properties - (b) Idempotent properties - (d) De Morgan's laws - (e) Commutative properties…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{symbols in a given alphabet. Definition 1.8 Let A be a set. A ′ = U -A is the set of all elements not in A. Example 1.3 Let A be the set of even integers and U be the set of integers. Then A ′ is the set of odd integers. Example 1.4 Let A = \{ x : x collects coins \} , then A ′ = …}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 10. ph-d7f4682645e561714633 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
Example 1.3 Let A be the set of even integers and U be the set of integers. Then A ′ is the set of odd integers. Example 1.4 Let A = { x : x collects coins } , then A ′ = { x : x does not collect coins } . The proof of the following theorem is left to the reader. Theorem 1.1 Let A, B, and C be subsets of the universal set U (a) Distributive properties - (b) Idempotent properties - (d) De Morgan's laws - (e) Commutative properties - (f) Associative laws - (g) Identity properties …
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{Example 1.3 Let A be the set of even integers and U be the set of integers. Then A ′ is the set of odd integers. Example 1.4 Let A = \{ x : x collects coins \} , then A ′ = \{ x : x does not collect coins \} . The proof of the following theorem is left to the reader. Theorem 1.1 Let…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 11. ph-ef5bd99d8def10e5468a — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
the set of integers. Then A ′ is the set of odd integers. Example 1.4 Let A = { x : x collects coins } , then A ′ = { x : x does not collect coins } . The proof of the following theorem is left to the reader. Theorem 1.1 Let A, B, and C be subsets of the universal set U (a) Distributive properties - (b) Idempotent properties - (d) De Morgan's laws - (e) Commutative properties - (f) Associative laws - (g) Identity properties - (h) Complement propertie…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{the set of integers. Then A ′ is the set of odd integers. Example 1.4 Let A = \{ x : x collects coins \} , then A ′ = \{ x : x does not collect coins \} . The proof of the following theorem is left to the reader. Theorem 1.1 Let A, B, and C be subsets of the universal set U (a) Dist…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 12. ph-63a34ca549693e0b0322 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
. Example 1.4 Let A = { x : x collects coins } , then A ′ = { x : x does not collect coins } . The proof of the following theorem is left to the reader. Theorem 1.1 Let A, B, and C be subsets of the universal set U (a) Distributive properties - (b) Idempotent properties - (d) De Morgan's laws - (e) Commutative properties - (f) Associative laws - (g) Identity properties - (h) Complement properties - (c) Double Complement p…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{. Example 1.4 Let A = \{ x : x collects coins \} , then A ′ = \{ x : x does not collect coins \} . The proof of the following theorem is left to the reader. Theorem 1.1 Let A, B, and C be subsets of the universal set U (a) Distributive properties - (b) Idempotent properties - (d) De Morgan's laws - (e) Commutative properties - (f) Associative laws - (g) Identity properties - (h) Complement properties - (c) Double Complement p…
\end{verbatim}
```
13. ph-87de056ad9c386a6bf33 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
= { x : x does not collect coins } . The proof of the following theorem is left to the reader. Theorem 1.1 Let A, B, and C be subsets of the universal set U (a) Distributive properties - (b) Idempotent properties - (d) De Morgan's laws - (e) Commutative properties - (f) Associative laws - (g) Identity properties - (h) Complement properties - (c) Double Complement property - (b) Idempotent properties - (d) De…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling $ / $$)
$$\text{theorem is left to the reader. Theorem 1.1 Let A, B, and C be subsets of the universal set U (a) Distributive properties - (b) Idempotent properties - (d) De Morgan's laws - (e) Commutative properties - (b) Idempotent properties - (d) De Morgan's laws - (e) Commutative properties - (f) Associative laws - (g) Identity properties - (h) Complement properties - (c) Double Complement property Definition 1.9 The size or …
\end{verbatim}
```
</details>
15. ph-475b215467922c1908a6 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
. Theorem 1.1 Let A, B, and C be subsets of the universal set U (a) Distributive properties - (b) Idempotent properties - (d) De Morgan's laws - (e) Commutative properties - (f) Associative laws - (g) Identity properties - (h) Complement properties - (c) Double Complement property Definition 1.9 The size or cardinality of a finite set A…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{. Theorem 1.1 Let A, B, and C be subsets of the universal set U (a) Distributive properties - (b) Idempotent properties - (d) De Morgan's laws - (e) Commutative properties - (f) Associative la…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 16. ph-3aa788208ba01c01ea81 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
be subsets of the universal set U (a) Distributive properties - (b) Idempotent properties - (d) De Morgan's laws - (e) Commutative properties - (f) Associative laws - (g) Identity properties - (h) Complement properties - (c) Double Complement property Definition 1.9 The size or cardinality of a finite set A, denoted by | A | , is the nu…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{be subsets of the universal set U (a) Distributive properties - (b) Idempotent properties - (d) De Morgan's laws - (e) Commutative properties - (f) Associative laws - (b) Idempotent properties - (d) De Morgan's laws - (e) Commutative properties - (f) Associative laws - (g) Identity properties - (h) Complement properties - (c) Double Complement property Definition 1.9 The size or cardinality of a finite set A, denoted by | A | , is the nu…
\end{verbatim}
```
17. ph-d74d98f681db563c7baf — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
countable set. We see that there are two infinite sets, the countable sets and the uncountable sets with different cardinality; however, we shall soon see that there are an infinite number of infinite sets of different cardinality. Further discussion of cardinality will be continued in the appendices. Definition 1.10 Let A and B be sets. The Cartesian product of A and B, denoted by A × B is the set { ( a , b ) : a ∈ A and b ∈ B } . For example, let A = { a , b } and B = { 1 , 2 , 3 } , then ThefamiliarCartesianplane R × R is the set of all ordered pairs of real nu…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{countable set. We see that there are two infinite sets, the countable sets and the uncountable sets with different cardinality; however, we shall soon see that there are an infinite number of infinite sets of different cardinality. Further discussion of cardinality will be conti…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 18. ph-f9dc26fbcc1aa4952716 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
nition 1.10 Let A and B be sets. The Cartesian product of A and B, denoted by A × B is the set { ( a , b ) : a ∈ A and b ∈ B } . For example, let A = { a , b } and B = { 1 , 2 , 3 } , then ThefamiliarCartesianplane R × R is the set of all ordered pairs of real numbers. Note that for finite sets | A × B | = | A | × | B | . Definition 1.11 The power set of a set A, denoted by P ( A ) , is the set of all subsets of A. For example the power set of { a , b , c } is In the finite case, it can be easily shown that | P ( A ) | = 2 | A | . ## E…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{nition 1.10 Let A and B be sets. The Cartesian product of A and B, denoted by A × B is the set \{ ( a , b ) : a ∈ A and b ∈ B \} . For example, let A = \{ a , b \} and B = \{ 1 , 2 , 3 \} , then ThefamiliarCartesianplane R × R is the set of all ordered pai…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 19. ph-b7975e77e998f69a5110 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
, b , c } is In the finite case, it can be easily shown that | P ( A ) | = 2 | A | . ## Exercises - (1) State which of the following are true and which are false: 2. (a) {∅} ⊆ A for an arbitrary set A 3. (c) { a , b , c } ⊆ { a , b , { a , b , c }} . 4. (b) ∅ ⊆ A for an arbitrary set A . 5. (d) { a , b , c } ∈ { a , b , { a , b , c }} . - (2) Prove Theorem 1.1. Let A , B , and C be subsets of the universal set U . 7. (e) A ∈ P ( A ). 8. (a) Idempotent property - (b) Double Complement property In the finite case, it can be easily shown that | P ( A ) | = 2 | A | . \#\# Exercises - (1) State which of the following are true and which are false: 2. (a) \{∅\} ⊆ A for an arbitrary set A 3. (c) \{ a , b , c \} ⊆ \{ a , b , \{ a , b , c \}\} .…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling $ / $$)
$$\text{it can be easily shown that | P ( A ) | = 2 | A | . \#\# Exercises - (1) State which of the following are true and which are false: 2. (a) \{∅\} ⊆ A for an arbitrary set A 3. (c) \{ a , b , c \} ⊆ \{ a , b , \{ a , b , c \}\} . 4. (b) ∅ ⊆ A for an arbitrary set A . 5. (d) \{ a , b , c \} ∈ …}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 21. ph-d567ed1997f25b39d430 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
P ( A ) | = 2 | A | . ## Exercises - (1) State which of the following are true and which are false: 2. (a) {∅} ⊆ A for an arbitrary set A 3. (c) { a , b , c } ⊆ { a , b , { a , b , c }} . 4. (b) ∅ ⊆ A for an arbitrary set A . 5. (d) { a , b , c } ∈ { a , b , { a , b , c }} . - (2) Prove Theorem 1.1. Let A , B , and C be subsets of the universal set U . 7. (e) A ∈ P ( A ). 8. (a) Idempotent property - (b) Double Complement property - . - (c) De Morgan's laws ## (d) Commutative properties - (b) Double Complement property - . - (c) De Morgan's laws ## (d) Commutative properties - (b) Double Complement property - . - (c) De Morgan's laws ## (d) Commutative properties - (e) Associative properties - (f) Distributive …
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{ch are false: 2. (a) \{∅\} ⊆ A for an arbitrary set A 3. (c) \{ a , b , c \} ⊆ \{ a , b , \{ a , b , c \}\} . 4. (b) ∅ ⊆ A for an arbitrary set A . 5. (d) \{ a , b , c \} ∈ \{ a , b , \{ a , b , c \}\} . - (2) Prove Theorem 1.1. Let A , B , and C be subsets of the universal set U . 7. (e) A ∈…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 23. ph-6e4246e008ba8f3e3c70 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
a , b , c } ⊆ { a , b , { a , b , c }} . 4. (b) ∅ ⊆ A for an arbitrary set A . 5. (d) { a , b , c } ∈ { a , b , { a , b , c }} . - (2) Prove Theorem 1.1. Let A , B , and C be subsets of the universal set U . 7. (e) A ∈ P ( A ). 8. (a) Idempotent property - (b) Double Complement property - . - (c) De Morgan's laws ## (d) Commutative properties - (e) Associative properties - (f) Distributive properties - (b) Double Complement property - . - (c) De Morgan's laws ## (d) Commutative properties - (e) Associative properties - (f) Distributive properties - (b) Double Complement property - . - (c) De Morgan's laws ## (d) Commutative properties - (e) Associative properties - (f) Distributive properties - (g) Identity properties ## (h) Complement propertie…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{arbitrary set A . 5. (d) \{ a , b , c \} ∈ \{ a , b , \{ a , b , c \}\} . - (2) Prove Theorem 1.1. Let A , B , and C be subsets of the universal set U . 7. (e) A ∈ P ( A ). 8. (a) Idempotent property - (b) Double Complement property - (b) Double Complement property - . - (c) De Morgan's laws ## (d) Commutative properties - (e) Associative properties - (f) Distributive properties - (g) Identity properties ## (h) Complement propertie…
\end{verbatim}
```
25. ph-19abd2424b1478deb377 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
, b , c } ∈ { a , b , { a , b , c }} . - (2) Prove Theorem 1.1. Let A , B , and C be subsets of the universal set U . 7. (e) A ∈ P ( A ). 8. (a) Idempotent property - (b) Double Complement property - . - (c) De Morgan's laws ## (d) Commutative properties - (e) Associative properties - (f) Distributive properties - (g) Identity properties ## (h) Complement properties - (4) If A B , what is A /D…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{, b , c \} ∈ \{ a , b , \{ a , b , c \}\} . - (2) Prove Theorem 1.1. Let A , B , and C be subsets of the universal set U . 7. (e) A ∈ P ( A ). 8. (a) Idempotent property - (b) Double Complement property - (b) Double Complement property - . - (c) De Morgan's laws ## (d) Commutative properties - (e) Associative properties - (f) Distributive properties - (g) Identity properties ## (h) Complement properties - (4) If A B , what is A /D…
\end{verbatim}
```
26. ph-d6955887337419bc6030 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
A ∈ P ( A ). 8. (a) Idempotent property - (b) Double Complement property - . - (c) De Morgan's laws ## (d) Commutative properties - (e) Associative properties - (f) Distributive properties - (g) Identity properties ## (h) Complement properties - (4) If A B , what is A /Delta1 B ? - (3) Given a set A ∈ P ( C ), find a set B such that A /…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{A ∈ P ( A ). 8. (a) Idempotent property - (b) Double Complement property - . - (c) De Morgan's laws \#\# (d) Commutative properties - (e) Associative properties - (b) Double Complement property - . - (c) De Morgan's laws ## (d) Commutative properties - (e) Associative properties - (f) Distributive properties - (g) Identity properties ## (h) Complement properties - (4) If A B , what is A /Delta1 B ? - (3) Given a set A ∈ P ( C ), find a set B such that A /…
\end{verbatim}
```
27. ph-04619380f9ea62386d0f — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
property - (b) Double Complement property - . - (c) De Morgan's laws ## (d) Commutative properties - (e) Associative properties - (f) Distributive properties - (g) Identity properties ## (h) Complement properties - (4) If A B , what is A /Delta1 B ? - (3) Given a set A ∈ P ( C ), find a set B such that A /Delta1 B = ∅ . - (5) Using the …
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{property - (b) Double Complement property - . - (c) De Morgan's laws \#\# (d) Commutative properties - (e) Associative properties - (f) …}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 28. ph-c7b3d9fda01e970fb153 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
-decoded --> - (3) Given a set A ∈ P ( C ), find a set B such that A /Delta1 B = ∅ . - (5) Using the properties in Theorem 1.1 prove that A ∩ ( B /Delta1 C ) = ( A ∩ B ) /Delta1 ( A ∩ C ) . 3. ⊆ - (6) Use induction to prove that for any finite set A , | A | < | P ( A ) | . 5. (8) 6. Prove using the properties in Theorem 1.1 - (7) (Russell's Paradox) Let S be the set of all sets. Then S ∈ S . Obviously ∅ / ∈ ∅ . Let W = { A : A / ∈ A } . Discuss whether W ∈ W . - (9) Use the fact that A ∩ ( A ∪ B ) = A to prove that A ∪ ( A ∩ B ) = A…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{-decoded --> - (3) Given a set A ∈ P ( C ), find a set B such that A /Delta1 B = ∅ . - (5) Using the properties in Theorem 1.1 prove that A ∩ ( B /Delta1 C ) = ( A ∩ B ) /Delta1 ( A ∩ C ) . 3. ⊆ - (6) Use induction to prove that for any finite set A …}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 29. ph-9bc5aaf6a7e525d7b926 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
B = ∅ . - (5) Using the properties in Theorem 1.1 prove that A ∩ ( B /Delta1 C ) = ( A ∩ B ) /Delta1 ( A ∩ C ) . 3. ⊆ - (6) Use induction to prove that for any finite set A , | A | < | P ( A ) | . 5. (8) 6. Prove using the properties in Theorem 1.1 - (7) (Russell's Paradox) Let S be the set of all sets. Then S ∈ S . Obviously ∅ / ∈ ∅ . Let W = { A : A / ∈ A } . Discuss whether W ∈ W . - (9) Use the fact that A ∩ ( A ∪ B ) = A to prove that A ∪ ( A ∩ B ) = A . - (10) Prove that if two disjoint sets are countable, then their union is …
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{B = ∅ . - (5) Using the properties in Theorem 1.1 prove that A ∩ ( B /Delta1 C ) = ( A ∩ B ) /Delta1 ( A ∩ C ) . 3. ⊆ - (6) Use induction to prove that for any finite set A , | A | \< | P ( A ) | . 5. (8) 6. Prove using the properties in Theorem 1.1 - (7) (Russell's Paradox) L…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 30. ph-4275a05a48c6d144dd9e — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
S . Obviously ∅ / ∈ ∅ . Let W = { A : A / ∈ A } . Discuss whether W ∈ W . - (9) Use the fact that A ∩ ( A ∪ B ) = A to prove that A ∪ ( A ∩ B ) = A . - (10) Prove that if two disjoint sets are countable, then their union is countable. ## 1.2 Relations Definition 1.12 Given sets A and B, any subset R of A × B is a relation between A and B. If ( a , b ) ∈ R , this is often denoted by a R b. If A = B, R is said to be a relation on A. Note that relations need not have any particular property nor even be describ…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{S . Obviously ∅ / ∈ ∅ . Let W = \{ A : A / ∈ A \} . Discuss whether W ∈ W . - (9) Use the fact that A ∩ ( A ∪ B ) = A to prove that A ∪ ( A ∩ B ) = A . - (10) Prove that if two disjoint sets are countable, then their union …}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 31. ph-74809c467ed3f44bc582 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
sets are countable, then their union is countable. ## 1.2 Relations Definition 1.12 Given sets A and B, any subset R of A × B is a relation between A and B. If ( a , b ) ∈ R , this is often denoted by a R b. If A = B, R is said to be a relation on A. Note that relations need not have any particular property nor even be describable. Obviously we will be interested in those relations which are describable and have particular properties which will be shown later. is a relation between A and B . Example 1.7 If …
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{sets are countable, then their union is countable. \#\# 1.2 Relations Definition 1.12 Given sets A and B, any subset R of A × B is a relation between A and B. If ( a , b ) ∈ R , this is often denoted by a R b. If A = B, R is said to be a relation on A. …}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 32. ph-94aba14c4794010c12c6 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
ations Definition 1.12 Given sets A and B, any subset R of A × B is a relation between A and B. If ( a , b ) ∈ R , this is often denoted by a R b. If A = B, R is said to be a relation on A. Note that relations need not have any particular property nor even be describable. Obviously we will be interested in those relations which are describable and have particular properties which will be shown later. is a relation between A and B . Example 1.7 If A is the set of people, then a R b if a and b are cousins is …
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{ations Definition 1.12 Given sets A and B, any subset R of A × B is a relation between A and B. If ( a , b ) ∈ R , this is often denoted by a R b. If A = B, R is said to be a relation on A. Note that relations need not have any particular property no…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 33. ph-3460b63f4957f5791cc6 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
Example 1.8 The domain and range of the relation { ( x , y ) : x 2 + y 2 = 4 } are -2 ≤ x ≤ 2 and -2 ≤ y ≤ 2 respectively. Example 1.9 The relation R is on the set of people. The domain and range of R is the set of people who have cousins. Definition 1.14 Let R be a relation between A and B. The inverse of the relation R denoted by R -1 is a relation been B and A, defined by R -1 = { ( b , a ) : ( a , b ) ∈ R } . Example 1.10 If A = { a , b , c , d , e } and B = { 1 , 2 , 3 , 4 , 5 } , and is a relation between A and B then is a relati…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{Example 1.8 The domain and range of the relation \{ ( x , y ) : x 2 + y 2 = 4 \} are -2 ≤ x ≤ 2 and -2 ≤ y ≤ 2 respectively. Example 1.9 The relation R is on the set of people. The domain and range of R is the set of people who have cousins. Definition 1.14 Let R be a relation bet…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 34. ph-5f4571d20dee85c44fc4 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
2 + y 2 = 4 } are -2 ≤ x ≤ 2 and -2 ≤ y ≤ 2 respectively. Example 1.9 The relation R is on the set of people. The domain and range of R is the set of people who have cousins. Definition 1.14 Let R be a relation between A and B. The inverse of the relation R denoted by R -1 is a relation been B and A, defined by R -1 = { ( b , a ) : ( a , b ) ∈ R } . Example 1.10 If A = { a , b , c , d , e } and B = { 1 , 2 , 3 , 4 , 5 } , and is a relation between A and B then is a relation between B and A . Definition 1.15…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{2 + y 2 = 4 \} are -2 ≤ x ≤ 2 and -2 ≤ y ≤ 2 respectively. Example 1.9 The relation R is on the set of people. The domain and range of R is the set of people who have cousins. Definition 1.14 Let R be a relation between A and B. The inverse of the relation R denoted by R -1 is a …}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 35. ph-d36ebda1d19c1942c397 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
ple 1.9 The relation R is on the set of people. The domain and range of R is the set of people who have cousins. Definition 1.14 Let R be a relation between A and B. The inverse of the relation R denoted by R -1 is a relation been B and A, defined by R -1 = { ( b , a ) : ( a , b ) ∈ R } . Example 1.10 If A = { a , b , c , d , e } and B = { 1 , 2 , 3 , 4 , 5 } , and is a relation between A and B then is a relation between B and A . Definition 1.15 Let R be a relation between A and B, and let S be a relation …
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{ple 1.9 The relation R is on the set of people. The domain and range of R is the set of people who have cousins. Definition 1.14 Let R be a relation between A and B. The inverse of the relation R denoted by R -1 is a relation been B and A, defined by R -1 = \{ ( b , a ) : ( a , b…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 36. ph-64bb8d9bfab2524d51d0 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
ple 1.10 If A = { a , b , c , d , e } and B = { 1 , 2 , 3 , 4 , 5 } , and is a relation between A and B then is a relation between B and A . Definition 1.15 Let R be a relation between A and B, and let S be a relation between B and C. The composition of R and S , denoted by S ◦ R is a relation between A and C defined by ( a , c ) ∈ S ◦ R if there exists b ∈ B such that ( a , b ) ∈ R and ( b , c ) ∈ S . be a relation between A and B . Then, as shown above is a relation between A and B then is a relation between B and A . Definition 1.15 Let R be a relation between A and B…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling $ / $$)
$$\text{ula-not-decoded --> is a relation between A and B then is a relation between B and A . Definition 1.15 Let R be a relation between A and B, and let S be a relation between B and C. The composition of R and S , denoted by …}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 38. ph-9d488c2d859596c3609d — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
mula-not-decoded --> is a relation between B and A . Definition 1.15 Let R be a relation between A and B, and let S be a relation between B and C. The composition of R and S , denoted by S ◦ R is a relation between A and C defined by ( a , c ) ∈ S ◦ R if there exists b ∈ B such that ( a , b ) ∈ R and ( b , c ) ∈ S . be a relation between A and B . Then, as shown above is a relation between B , and A , is a relation on B , and is a relation on A . Exa…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{mula-not-decoded --> is a relation between B and A . Definition 1.15 Let R be a relation between A and B, and let S be a relation between B and C. The composition of R and S , denoted by S ◦ R is a relation between A and C defined by ( a , c ) ∈ S ◦ …}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 39. ph-8c81b6c8834008ad4787 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
!-- formula-not-decoded --> Definition 1.15 Let R be a relation between A and B, and let S be a relation between B and C. The composition of R and S , denoted by S ◦ R is a relation between A and C defined by ( a , c ) ∈ S ◦ R if there exists b ∈ B such that ( a , b ) ∈ R and ( b , c ) ∈ S . be a relation between A and B . Then, as shown above is a relation between B , and A , is a relation on B , and is a relation on A . Example 1.13 If R = { ( x , y ) : y = x + 5 } and S = { (…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{!-- formula-not-decoded --> Definition 1.15 Let R be a relation between A and B, and let S be a relation between B and C. The composition of R and S , denoted by S ◦ R is a relation between A and C defined by ( a , c ) ∈ S ◦ R if there exists b ∈ B such that ( a , b ) ∈ R and ( …}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 40. ph-6c86b22eaf4da3d170e7 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
conclude that a and a are siblings, which we know is not true. Example 1.15 Let A be the set of all people and a R b if a and b have the same parents. The relation R is reflexive since everyone has the same parents as themselves. It is symmetric since if a and b have the same parents, b and a have the same parents. It is also transitive since if a and b have the same parents and b and c have the same parents, then a and c have the same parents. Example 1.16 Let A = { a , b , c , d , e } and R is not reflexive since ( e , e ) / ∈ R . It is not symmetric because ( a…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{conclude that a and a are siblings, which we know is not true. Example 1.15 Let A be the set of all people and a R b if a and b have the same parents. The relation R is reflexive since everyone has the same parents as themselves. It is symmetric since if a and b have the same pa…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 41. ph-7beb04fc04e000d14bb5 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
, a ) ∈ R , but d /negationslash= a . It is not transitive since ( a , c ) , ( c , e ) , but ( a , e ) / . ∈ R ∈ R Example 1.17 Let R betherelation on Z defined by a R b if a -b is a multiple of 5. Certainly a -a = 0 is a multiple of 5, so R is reflexive. If a -b is a multiple of 5, then a -b = 5 k for some integer k . Hence b -a = 5( -k ) is a multiple of 5, so R is symmetric. If a -b is a multiple of 5 and b -c is a multiple of 5, then a -b = 5 k and b -c = 5 m for some integers k and m . so that a -c is a multiple of 5. Hence R is transitive. Definition 1.17 Ar…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{, a ) ∈ R , but d /negationslash= a . It is not transitive since ( a , c ) , ( c , e ) , but ( a , e ) / . ∈ R ∈ R Example 1.17 Let R betherelation on Z defined by a R b if a -b is a multiple of 5. Certainly a -a = 0 is a multiple of 5, so R is reflexive. If a -b is a multiple o…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 42. ph-c17d7f08137a8fe5ea6e — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
R 1 be the relation on Z defined by R 1 = { ( m , n ) : m -n } is divisible by 5. R 1 is shown above to be an equivalence relation on the integers. Example 1.19 Let A be the set of all people. Define R 2 by a R 2 b if a and b are the same age. This is easily shown to be an equivalence relation. An equivalence relation on a set A divides A into nonempty subsets that are mutually exclusive or disjoint , meaning that no two of them have an element in common. In the first example above, the sets contain elements that are related to each other and no element in one set…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{R 1 be the relation on Z defined by R 1 = \{ ( m , n ) : m -n \} is divisible by 5. R 1 is shown above to be an equivalence relation on the integers. Example 1.19 Let A be the set of all people. Define R 2 by a R 2 b if a and b are the same age. This is easily shown to be an equiv…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 43. ph-eb0e13a183677a7f1d84 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
two sets. (See the definition of partition below.) Notation 1.1 Let R be an equivalence relation on a set A and a ∈ A . Then [ a ] R = { x : x R a } . If the relation is understood, then [ a ] R is simply denoted by [ a ]. Let [ A ] R = { [ a ] R : a ∈ A } . Definition 1.18 Let A and I be nonempty sets and 〈 A 〉 = { Ai : i ∈ I } be a set of nonempty subsets of A. The set 〈 A 〉 is called a partition of A if both of the following are satisfied: - (a) Ai ∩ Aj = ∅ for all i /negationslash= j . Theorem 1.3 A nonempty set of subsets 〈 A 〉 of a set A is a partition of A …
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{two sets. (See the definition of partition below.) Notation 1.1 Let R be an equivalence relation on a set A and a ∈ A . Then [ a ] R = \{ x : x R a \} . If the relation is understood, then [ a ] R is simply denoted by [ a ]. Let [ A ] R = \{ [ a ] R : a ∈ A \} . Definition 1.18 Let …}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 44. ph-60553470583019d89c25 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
t A ( if it exists ) is called the greatest element of A. For a subset B of a poset A, an element a of A is a lower bound of B if a ≤ b (or b ≥ a ) for all b in B. The element a is called a greatest lower bound (glb) of B if ( i ) a is a lower bound of B and ( ii ) if any other element a ′ of A is a lower bound of B, then a ≥ a ′ . The greatest lower bound for the entire poset A ( if it exists ) is called the least element of A. Example 1.22 Let C = { a , b , c } and X be the power set of C . Define the relation ≤ on X by T ≤ V if T ⊆ V . By definition, { a , b } …
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{t A ( if it exists ) is called the greatest element of A. For a subset B of a poset A, an element a of A is a lower bound of B if a ≤ b (or b ≥ a ) for all b in B. The element a is called a greatest lower bound (glb) of B if ( i ) a is a lower bound of B and ( ii ) if any other …}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 45. ph-0dc370ffc35420cebd9c — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
ement b ∈ B, there is an element a ∈ A so that b = f ( a ) . Definition 1.27 If f : A → B, and f ( a ) = f ( a ′ ) ⇒ a = a ′ for all a , a ′ ∈ A then f is one-to-one . It is also called a monomorphism or injection . Definition 1.28 If f : A → B is one-to-one and onto, then f is called a one-to-one correspondence or bijection . If A is finite, then f is also called a permutation . Notation 1.2 If f is a permutation on the set { 1 , 2 , 3 , . . . , n } , then it can be represented in the form Thus if f ( a ) = b , f ( b ) = d , f ( c ) = a , and f ( d ) = c , we may…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{ement b ∈ B, there is an element a ∈ A so that b = f ( a ) . Definition 1.27 If f : A → B, and f ( a ) = f ( a ′ ) ⇒ a = a ′ for all a , a ′ ∈ A then f is one-to-one . It is also called a monomorphism or injection . Definition 1.28 If f : A → B is one-to-one and onto, then f is …}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 46. ph-7a47e9633a91369b07fd — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
f ( f -1 ( b )) = b , f is onto. By symmetry, f -1 Assume f : A → B is a bijection. Define the relation f -1 on B × A by f -1 ( b ) = a if f ( a ) = b . Let b ∈ B and choose a so that f ( a ) = b . This is possible since f is onto. Therefore f -1 ( b ) = a and f -1 has domain B . If f -1 ( b ) = a and f -1 ( b ) = a ′ , then f ( a ) = b and f ( a ′ ) = b . But since f is one-to-one, a = a ′ . Therefore f -1 is well defined and hence f -1 is a function. By definition f ◦ f -1 = f -1 ◦ f = I . The proof of the following theorem is left to the reader: Theorem 1.7 Let…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{f ( f -1 ( b )) = b , f is onto. By symmetry, f -1 Assume f : A → B is a bijection. Define the relation f -1 on B × A by f -1 ( b ) = a if f ( a ) = b . Let b ∈ B and choose a so that f ( a ) = b . This is possible since f is onto. Therefore f -1 ( b ) = a and f -1 has domain B …}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 47. ph-3213bbfd61a14ba2f46c — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
f ◦ g ) -1 = g -1 ◦ f -1 . - (3) Give an example of a function f and sets A 1 , A 2 ⊆ A such that f ( A 1 ∩ A 2 ) /negationslash= f ( A 1 ) ∩ f ( A 2 ). - (5) Prove that if f ◦ g is onto, then f is onto. - (4) Prove that if f ◦ g is one-to-one then g is one-to-one. ## 1.4 Semigroups In the following function /star : S × S → S we shall use the notation a /star a ′ for /star (( a , a ′ )). Definition 1.32 A semigroup is a nonempty set S together with a function /star from S × S → S such that The function or operation /star with this property is called associative . …
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{f ◦ g ) -1 = g -1 ◦ f -1 . - (3) Give an example of a function f and sets A 1 , A 2 ⊆ A such that f ( A 1 ∩ A 2 ) /negationslash= f ( A 1 ) ∩ f ( A 2 ). - (5) Prove that if f ◦ g is onto, then f is onto. - (4) Prove that if f ◦ g is one-to-one then g is one-to-one. \#\# 1.4 Semigr…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 48. ph-8dbedd042f1d747dced4 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
th the operation defined in the previous definition and φ R : S → S / R defined by φ R ( s ) = s R is a homomorphism. Theorem 1.16 Let f : A → B be a homomorphism and R be the congruence a R a ′ iff f ( a ) = f ( a ′ ) , then there exists a homomorphism g : A / R → B defined by g ( a R ) = f ( a ) . Hence g ◦ φ R = f .  R Proof We showed in Theorem 1.9 that g is a function. /square Theorem 1.17 Let f : A / R → B be a function and S ⊆ R , so if a S …
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{th the operation defined in the previous definition and φ R : S → S / R defined by φ R ( s ) = s R is a homomorphism. Theorem 1.16 Let f : A → B be a homomorphism and R be the congruence a R a ′ iff f ( a ) = f ( a ′ ) , then there exists a homomorphism g : A / R → B defined by …}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 49. ph-45b475758c590705285b — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
, so if a S a ′ implies a R a ′ , then there exist functions g : A / S → B and i : A / S → A / R such that f ◦ i = g.  S Proof Let i : A / S → A / R be defined by i ( a S ) = a R and g : A / S → B by g ( a S ) = f ( a R ) . The function i is trivially well defined and a homomorphism. The proof that g is a function is similar to the proof of Theorem 1.9. (See Theorem 1.10). /square We already know that the set of all functions from a set A to itself…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{, so if a S a ′ implies a R a ′ , then there exist functions g : A / S → B and i : A / S → A / R such that f ◦ i = g.  S Proof Let i : A / S → A / R be defined b…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 50. ph-f8e7dcc6b185ba8dd0ea — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
already know that the set of all functions from a set A to itself form a semigroup since for a ∈ A , and functions f , g , and h from A to itself, (( f ◦ ( g ◦ h ))( a ) = (( f ◦ g ) ◦ h )( a ) = f ( g ( h ( a ). Also since f , g , and h are relations we have already proven that ( f ( g h ) ( f g ) h . Conversely, given a semigroup S , and s ∈ S we can define a function φ s : S → S by φ s ( t ) = st for all t ∈ S . Let T S = { φ s : S → S for s ∈ S } . For all s , t , and u in S , ◦ ◦ = ◦ ◦ and φ st = ( φ s ◦ φ t ). Let τ : S → T S be defined by τ ( s ) = φ s . Th…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{already know that the set of all functions from a set A to itself form a semigroup since for a ∈ A , and functions f , g , and h from A to itself, (( f ◦ ( g ◦ h ))( a ) = (( f ◦ g ) ◦ h )( a ) = f ( g ( h ( a ). Also since f , g , and h are relations we have already proven that…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 51. ph-4051a69818f20233e019 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
self, (( f ◦ ( g ◦ h ))( a ) = (( f ◦ g ) ◦ h )( a ) = f ( g ( h ( a ). Also since f , g , and h are relations we have already proven that ( f ( g h ) ( f g ) h . Conversely, given a semigroup S , and s ∈ S we can define a function φ s : S → S by φ s ( t ) = st for all t ∈ S . Let T S = { φ s : S → S for s ∈ S } . For all s , t , and u in S , ◦ ◦ = ◦ ◦ and φ st = ( φ s ◦ φ t ). Let τ : S → T S be defined by τ ( s ) = φ s . The function τ is a homomorphism since Theorem 1.18 Every semigroup is isomorphic to a semigroup of functions from…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{self, (( f ◦ ( g ◦ h ))( a ) = (( f ◦ g ) ◦ h )( a ) = f ( g ( h ( a ). Also since f , g , and h are relations we have already proven that ( f ( g h ) ( f g ) h . Conversely, given a semigroup S , and s ∈ S we can define a function φ s : S → S by φ s ( t ) = st for all t ∈ S . L…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 52. ph-7bbd5f73f8caaa75d3b6 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
quence a 1 a 2 a 3 a 4 . . . an where ai ∈ /Sigma1 . Thus if /Sigma1 = { a , b } , then aab , a , baba , bbbbb , and baaaaa would all be strings of symbols of /Sigma1 . In addition we include an empty string denoted by λ which has no symbols in it. Definition 2.2 Let /Sigma1 ∗ denote the set of all strings of /Sigma1 including the empty string. Define the binary operation ◦ called concatenation on /Sigma1 ∗ as follows: If a 1 a 2 a 3 a 4 . . . an and b 1 b 2 b 3 b 4 . . . bm ∈ /Sigma1 ∗ then If S and T are subsets of /Sigma1 ∗ then S ◦ T = { s ◦ t : s ∈ S , t ∈ T …
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{quence a 1 a 2 a 3 a 4 . . . an where ai ∈ /Sigma1 . Thus if /Sigma1 = \{ a , b \} , then aab , a , baba , bbbbb , and baaaaa would all be strings of symbols of /Sigma1 . In addition we include an empty string denoted by λ which has no symbols in it. Definition 2.2 Let /Sigma1 ∗ d…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 53. ph-ed9dcf24163e545dc5f0 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
the submonoid generated by a subset of a monoid described in Chapter 1. Definition 2.3 Let B be a subset of /Sigma1 ∗ then B ∗ is the set of all strings or words formed by concatenating words from B together with the empty string, i.e. B ∗ = { w 1 w 2 . . . w n : w i ∈ B } ∪ { λ } . If ∅ denotes the empty set then ∅ ∗ = { λ } . The symbol ∗ is called the Kleene star and is named after the mathematician and logician Stephen Cole Kleene. Note that /Sigma1 ∗ is consistent with this definition. Let A + be the set consisting of all finite p…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{the submonoid generated by a subset of a monoid described in Chapter 1. Definition 2.3 Let B be a subset of /Sigma1 ∗ then B ∗ is the set of all strings or words formed by concatenating words from B together with the empty string, i.e. B ∗ = \{ w 1 w 2 . . . w n : w i ∈ B \} ∪ \{ λ…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 54. ph-69ad2bc19fdff4de8e90 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
ubset of a monoid described in Chapter 1. Definition 2.3 Let B be a subset of /Sigma1 ∗ then B ∗ is the set of all strings or words formed by concatenating words from B together with the empty string, i.e. B ∗ = { w 1 w 2 . . . w n : w i ∈ B } ∪ { λ } . If ∅ denotes the empty set then ∅ ∗ = { λ } . The symbol ∗ is called the Kleene star and is named after the mathematician and logician Stephen Cole Kleene. Note that /Sigma1 ∗ is consistent with this definition. Let A + be the set consisting of all finite products of elements of a nonem…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{ubset of a monoid described in Chapter 1. Definition 2.3 Let B be a subset of /Sigma1 ∗ then B ∗ is the set of all strings or words formed by concatenating words from B together with the empty string, i.e. B ∗ = \{ w 1 w 2 . . . w n : w i ∈ B \} ∪ \{ λ \} . If ∅ denotes the empty se…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 55. ph-4de411ab92dea32624bd — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
Sigma1 and the symbols ∅ , λ, ∗ , ∨ , ( , and ) . The symbol λ is used to denote the symbol ∅ ∗ . - (i) The symbol ∅ is a regular expression and for every a ∈ /Sigma1 , the symbol a is a regular expression. - (ii) If w 1 and w 2 are regular expressions, then w 1 w 2 , w 1 ∨ w 2 , w ∗ 1 , and ( w 1 ) are regular expressions. - (iii) There are no regular expressions which are not generated by ( i ) and ( ii ) . Each expression corresponds to a set with the following correspondence £ defined by The image of a regular expression is a regul…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{Sigma1 and the symbols ∅ , λ, ∗ , ∨ , ( , and ) . The symbol λ is used to denote the symbol ∅ ∗ . - (i) The symbol ∅ is a regular expression and for every a ∈ /Sigma1 , the symbol a is a regular expression. - (ii) If w 1 and w 2 are regular expressions, then w 1 w 2 , w 1 ∨ w 2 …}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 56. ph-fbe6259853f2f78b7b20 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
∗ , ∨ , ( , and ) . The symbol λ is used to denote the symbol ∅ ∗ . - (i) The symbol ∅ is a regular expression and for every a ∈ /Sigma1 , the symbol a is a regular expression. - (ii) If w 1 and w 2 are regular expressions, then w 1 w 2 , w 1 ∨ w 2 , w ∗ 1 , and ( w 1 ) are regular expressions. - (iii) There are no regular expressions which are not generated by ( i ) and ( ii ) . Each expression corresponds to a set with the following correspondence £ defined by The image of a regular expression is a regular language. Regular languages…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{∗ , ∨ , ( , and ) . The symbol λ is used to denote the symbol ∅ ∗ . - (i) The symbol ∅ is a regular expression and for every a ∈ /Sigma1 , the symbol a is a regular expression. - (ii) If w 1 and w 2 are regular expressions, then w 1 w 2 , w 1 ∨ w 2 , w ∗ 1 , and ( w 1 ) are regu…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 57. ph-ee0acc1ee30386d7ed76 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
A : h ( a ) = ua v where only mortal symbols occur in u and v } . For each a in X, let Na be the least nonnegative integer for which h Na ( u v ) = λ . Let H = { h Na ( a ) : a ∈ X } . The fixed language L of h is the submonoid of A ∗ generated by H. The correspondence a ↔ h Na ( a ) is a one-to-one correspon- dence between X and H. Proof (1) H ∗ ⊆ L : Since h is a homomorphism it is sufficient to verify that each element h N ( a ) ( a ) of H is in L , which is confirmed by the calculation: (2) L ⊆ H ∗ : Let w be in L . Let a 1 , a 2 , a 3 , . . . , an be the subs…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{A : h ( a ) = ua v where only mortal symbols occur in u and v \} . For each a in X, let Na be the least nonnegative integer for which h Na ( u v ) = λ . Let H = \{ h Na ( a ) : a ∈ X \} . The fixed language L of h is the submonoid of A ∗ generated by H. The correspondence a ↔ h Na …}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 58. ph-88706cb48ec207ed6c8d — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
rds of length > 2 is not free. Corollary 2.2 If A is an alphabet having exactly n symbols, then no inclusion chain of distinct retracts of A ∗ has more than n + 1 retracts even when the retract { λ } is included. Corollary 2.3 If X is a key code and x n lies in X ∗ , then so does x. Corollary 2.4 If X is a key code and both u v and v u lie in X ∗ , then so do u and v . Let A = { a 1 , a 2 , a 3 , . . . , an } . A simple example of a longest possible inclusion chain of retracts in A ∗ is Each of these retracts, except the first, is maximal among the retracts con…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{rds of length \> 2 is not free. Corollary 2.2 If A is an alphabet having exactly n symbols, then no inclusion chain of distinct retracts of A ∗ has more than n + 1 retracts even when the retract \{ λ \} is included. Corollary 2.3 If X is a key code and x n lies in X ∗ , then so …}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 59. ph-92591839f1e9a8e4de4f — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
ng the retracts contained in its predecessor. In each case the number of generators of the subretract is one less than the number of generators of its predecessor. However, maximal proper subretracts of a retract can have many fewer generators: Proposition 2.2 Let n be a positive integer and A = { a 1 , a 2 , a 3 , . . . , an } an alphabet of n symbols. Let m be any positive integer less than n. Then A ∗ contains a maximal proper retract generated by exactly m words. Proof The set of m words is a key code for which K ∗ is a maximal proper retract of A ∗ . The veri…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{ng the retracts contained in its predecessor. In each case the number of generators of the subretract is one less than the number of generators of its predecessor. However, maximal proper subretracts of a retract can have many fewer generators: Proposition 2.2 Let n be a positiv…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 60. ph-a56fdfcba5b3132b450c — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
and both u v and v u lie in X ∗ , then so do u and v . ## 2.3 Semiretracts and lattices (Optional) The intersection of two retracts of the free monoid on a finite set A need not be a retract if A contains four or more symbols. Possibly the simplest example is the following one adapted from [ 7 ]: Let A = { a , b , c , d } . The sets { ab , ac , d } and { ba , c , da } are key codes and consequently the submonoids R and R ′ that they generated are retracts of A ∗ . However, their intersection is not only not a retract; it is not even finitely generated. The set d (…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{and both u v and v u lie in X ∗ , then so do u and v . \#\# 2.3 Semiretracts and lattices (Optional) The intersection of two retracts of the free monoid on a finite set A need not be a retract if A contains four or more symbols. Possibly the simplest example is the following one a…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 61. ph-b31ea07bb712add67363 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
always a complete lattice. By broadening our attention slightly we obtain a similarly attractive stability result for what we call semiretracts of free monoids: Definition 2.14 By a semiretract of A ∗ , we mean an intersection of a finite number of retracts of A ∗ . Each retract of A ∗ is also a semiretract. The clearest example of a semiretract that is not a retract is the example given previously: R ∩ R ′ = ( d ( ab ) ∗ ac ) ∗ . Some pairs of retracts have as their intersection a retract: As stated above, but not to be demonstrated here, if fewer than four alpha…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{always a complete lattice. By broadening our attention slightly we obtain a similarly attractive stability result for what we call semiretracts of free monoids: Definition 2.14 By a semiretract of A ∗ , we mean an intersection of a finite number of retracts of A ∗ . Each retract…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 62. ph-e8166ee4c007a92fc63b — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
e diagram  In this automaton, if three consecutive b s are read, then the automaton is in state s 3, which is a sink state and is not an acceptance state. This is the only way to get to s 3 and every other state is an acceptance state. Thus the language accepted by this automaton consists of all words which do not have three consecutive b s. An expression for this language is As previously mentioned, the automata that we have been discussing are ca…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{e diagram  In this automaton, if three consecutive b s are read, then the automaton is in state s 3, which is a sink state and is not an acceptance state. This i…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 63. ph-39b8eedbccfc645f0e48 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
ϒ as a set of rules, given a ∈ /Sigma1 and s ∈ Q , the rules may allow advancement to each of several states or there may not be a rule which does not allow it to go to any state after reading a in state s . In the latter case, the automaton is 'hung up' and can proceed no further. This cannot occur with a deterministic automaton. Although the definition of a nondeterministic automaton varies, we shall use the following definition: ## Definition 3.2 A nondeterministic automaton , denoted by consists of a finite alphabet /Sigma1 , a finite set Q of states, and a fu…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{ϒ as a set of rules, given a ∈ /Sigma1 and s ∈ Q , the rules may allow advancement to each of several states or there may not be a rule which does not allow it to go to any state after reading a in state s . In the latter case, the automaton is 'hung up' and can proceed no furth…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 64. ph-d1c5eb81e044ee1a45b6 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
there may not be a rule which does not allow it to go to any state after reading a in state s . In the latter case, the automaton is 'hung up' and can proceed no further. This cannot occur with a deterministic automaton. Although the definition of a nondeterministic automaton varies, we shall use the following definition: ## Definition 3.2 A nondeterministic automaton , denoted by consists of a finite alphabet /Sigma1 , a finite set Q of states, and a function called the transition function . The set Q contains an element s 0 and a sub…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{there may not be a rule which does not allow it to go to any state after reading a in state s . In the latter case, the automaton is 'hung up' and can proceed no further. This cannot occur with a deterministic automaton. Although the definition of a nondeterministic automaton va…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 65. ph-525bba209b8cb7717ecf — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
of P ( Q ), i.e. the set of subsets of Q , as states for the deterministic automaton which we are constructing. Some of these states may not be used since they do not occur on any path which leads to acceptance state. Hence they could be removed and greatly simplify the deterministic automaton created. However, for our purpose, we are only interested in showing that a deterministic automaton can be created. In general we have the following procedure for constructing a deterministic automaton from a nondeterministic automaton. - (1) Beg…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{of P ( Q ), i.e. the set of subsets of Q , as states for the deterministic automaton which we are constructing. Some of these states may not be used since they do not occur on any path which leads to acceptance state. Hence they could be removed and greatly simplify the determin…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 66. ph-dacc66717f95d38063f1 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
rministic automaton which we are constructing. Some of these states may not be used since they do not occur on any path which leads to acceptance state. Hence they could be removed and greatly simplify the deterministic automaton created. However, for our purpose, we are only interested in showing that a deterministic automaton can be created. In general we have the following procedure for constructing a deterministic automaton from a nondeterministic automaton. - (1) Begin with the state { s 0 } where s 0 is the start state of the non…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{rministic automaton which we are constructing. Some of these states may not be used since they do not occur on any path which leads to acceptance state. Hence they could be removed and greatly simplify the deterministic automaton created. However, for our purpose, we are only in…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 67. ph-604d706857011b1e1697 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
till read abbb . Assume that we have ( si , a w ) w ∈ /Sigma1 + . Thus the automaton is in state si and must still read a followed by w . The notation ( si , a w ) /turnstileleft ( s j , w ) means that the automaton has read a and moved from state si to state s j . Therefore ϒ ( si , a ) = s j . In the automaton  we have ( s 2 , bab ) /turnstileleft ( s 3 , ab ). We also have If we have ( si , w i ) /turnstileleft ( s j , w j ) /turnstileleft · · ·…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{till read abbb . Assume that we have ( si , a w ) w ∈ /Sigma1 + . Thus the automaton is in state si and must still read a followed by w . The notation ( si , a w ) /turnstileleft ( s j , w ) means that the automaton has read a and moved from state si to state s j . Therefore ϒ (…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 68. ph-024438a054482f985d16 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
onstruction, the set of states of M ′ is a subset of P ( Q ). The state s ′ 0 = E ( s 0), and F ′ is a set containing an element of F . For each element a of /Sigma1 , define ϒ ′ by ϒ ′ ( P , a ) = ⋃ p ∈ P E ( ϒ ( p , a )). We first show that M ′ is deterministic. It is certainly single valued. Further ϒ ′ ( P , a ) will always have a value even if it is the empty set. We must now show that M ( L ) = M ′ ( L ). To do this we show that for any states p and q in Q , and any word w in /Sigma1 ∗ for some P containing q . From this it will follow that for some P containing q . From this it will follow that for some P containing q . From this it will follow that for some P containing f , where f ∈ F . and it must be shown that We prove …
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{), and F ′ is a set containing an element of F . For each element a of /Sigma1 , define ϒ ′ by ϒ ′ ( P , a ) = ⋃ p ∈ P E ( ϒ ( p , a )). We first show that M ′ is deterministic. It is certainly single valued. Further ϒ ′ ( P , a ) will always have a value even if it is the empty…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 70. ph-855aeef646ca513f135b — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
. It is certainly single valued. Further ϒ ′ ( P , a ) will always have a value even if it is the empty set. We must now show that M ( L ) = M ′ ( L ). To do this we show that for any states p and q in Q , and any word w in /Sigma1 ∗ for some P containing q . From this it will follow that for some P containing f , where f ∈ F . and it must be shown that We prove this using induction of the length of w . If | w | = 0, then w = λ , for some P containing q . Now ( p , λ ) /turnstileleft ∗ ( q , λ ) if and only…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{. It is certainly single valued. Further ϒ ′ ( P , a ) will always have a value even if it is the empty set. We must now show that M ( L ) = M ′ ( L ). To do this we show that for any states p and q in Q , and any word w in /Sigma1 ∗ for some P conta…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 71. ph-dfd14e06ec821aaf4feb — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
ula-not-decoded --> for some P containing q . Now ( p , λ ) /turnstileleft ∗ ( q , λ ) if and only if q ∈ E ( p ); but since M ′ is deterministic and no letter is read, then P = E ( p ) and p ∈ E ( p ) . Therefore the statement is true if | w | = 0. ⇒ : Assume w = v a for some letter a and w and ( p , w ) /turnstileleft ∗ ( q , λ ) so that Assume the statement is true for all strings having nonnegative length k . We now have to prove the statement is true for any string w with length k + 1. where at the end, possibly no letters of the alphabet are read. Since ( p …
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{ula-not-decoded --> for some P containing q . Now ( p , λ ) /turnstileleft ∗ ( q , λ ) if and only if q ∈ E ( p ); but since M ′ is deterministic and no letter is read, then P = E ( p ) and p ∈ E ( p ) . Therefore the statement is true if | w | = 0. ⇒ : Assume w = v a for some l…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 72. ph-182761a057d36799e165 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
states. If they do, we can always relabel them. Since we want to begin in M 1, we let s 0 be the starting state of M so that s ′′ 0 = s 0. Since we want to finish in M 2, we let the set of acceptance states be F ′ so that F ′′ = F ′ . We define the rules for ϒ ′′ as follows. If the rule If in state si and a is read, go to state s j is in ϒ and s j is not an acceptance state then include this rule in ϒ ′′ . If s j is an acceptance state then include this rule in ϒ ′′ and also include the rule Hence there is the option of going to the state s j or skipping over to s…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{states. If they do, we can always relabel them. Since we want to begin in M 1, we let s 0 be the starting state of M so that s ′′ 0 = s 0. Since we want to finish in M 2, we let the set of acceptance states be F ′ so that F ′′ = F ′ . We define the rules for ϒ ′′ as follows. If …}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 73. ph-0c75b6e70ee8b3236db8 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
ge](./AutomataTheory_artifacts/image_000061_475e3e83df6fe2ff7c71da51a51ef85161d8f8c7b8f17a885e0294af64d160d3.png) occurs, where e 1 , e 2 , e 3 , · · · , e k are regular expressions, then replace it with the diagram   occurs, then replace it with the diagram More generally if the diagram 
$$\text{ge](./AutomataTheory\_artifacts/image\_000061\_475e3e83df6fe2ff7c71da51a51ef85161d8f8c7b8f17a885e0294af64d160d3.png) occurs, where e 1 , e 2 , e 3 , · · · , e k are regular expressions, then replace it with the diagram 
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 74. ph-3eb47af54e956a6d1cac — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
4692ce11cff48238ca8a33d702d3aa5aa2219c1008349b9b866e1e0773544.png)  occurs, then replace it with the diagram More generally if the diagram  occurs, where e 1 , e 2 , e 3 are regular expressions, then replace it with the diagram In particular, when e 2 = λ , then e 1 e ∗ 2 e 3 becomes e 1 e 3 so that the …
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{4692ce11cff48238ca8a33d702d3aa5aa2219c1008349b9b866e1e0773544.png)  occurs, then replace it with the diagram More generally if the d…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 75. ph-5168fd32d43991ff1108 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
_09a265b2e78d8222da71fc563beaf311e119039a9d8c7470becc6958af4dbabe.png) occurs, then replace it with the diagram More generally if the diagram  occurs, where e 1 , e 2 , e 3 are regular expressions, then replace it with the diagram In particular, when e 2 = λ , then e 1 e ∗ 2 e 3 becomes e 1 e 3 so that the diagram is replaced by the diagram 
$$\text{\_09a265b2e78d8222da71fc563beaf311e119039a9d8c7470becc6958af4dbabe.png) occurs, then replace it with the diagram More generally if the diagram 
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 76. ph-775e62be74475c114f1b — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
plete the proof, we need to show that R ( i , p , j ) is regular for 1 ≤ p ≤ n + 1 . We do this using induction. If p = 1, then there are no interior states in the path so R ( i , p , j ) = { a ∈ /Sigma1 : δ ( qi , a ) = qj } if i /negationslash= j and { λ } ∪ { a ∈ /Sigma1 : δ ( qi , a ) = qj } if i = j . Hence we have a finite set of elements of /Sigma1 and possibly λ in the set so it is a regular set. Assume R ( i , k , j ) is regular. The set of words R ( i , k + 1 , j ) can be defined as where the path from qi to qj may not pass through a state qm where m ≥ k…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{plete the proof, we need to show that R ( i , p , j ) is regular for 1 ≤ p ≤ n + 1 . We do this using induction. If p = 1, then there are no interior states in the path so R ( i , p , j ) = \{ a ∈ /Sigma1 : δ ( qi , a ) = qj \} if i /negationslash= j and \{ λ \} ∪ \{ a ∈ /Sigma1 : δ …}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 77. ph-b89a830f1e42472b5d35 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
g an interior state qm where m ≥ k . Since R ( i , k + 1 , j ) is formed using union, concatenation, and Kleene star of regular states, it is regular and hence L is regular. Since we have now shown that every regular expression is accepted by an automaton and that the language accepted by an automaton is regular, we have proven Kleene's Theorem. As a result of Kleene's Theorem, we discover two new properties about the regular languages: Theorem 3.4 If L 1 and L 2 are regular languages, then and L 1 ∩ L 2 are regular languages. Proof To show /Sigma1 ∗ -L 1 is regul…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{g an interior state qm where m ≥ k . Since R ( i , k + 1 , j ) is formed using union, concatenation, and Kleene star of regular states, it is regular and hence L is regular. Since we have now shown that every regular expression is accepted by an automaton and that the language a…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 78. ph-24b56b491b76bd202dec — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
t the automaton for /Sigma1 ∗ -L 1, simply change all of the terminal states in M 1 to nonterminal states and all of the nonterminal states to terminal states. As a result, all words that were accepted because the automaton stopped in a terminal state, are no longer accepted and all words which were not accepted are now accepted since the automaton will now stop in a terminal state after reading this word. To show that L 1 ∩ L 2 is a regular language we simply use the set theory property that This is most easily seen by thinking of /Sigma1 ∗ as the universe so tha…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{t the automaton for /Sigma1 ∗ -L 1, simply change all of the terminal states in M 1 to nonterminal states and all of the nonterminal states to terminal states. As a result, all words that were accepted because the automaton stopped in a terminal state, are no longer accepted and…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 79. ph-51a04293e9b636c85b2a — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
, and we are finished. In the graph shown below, only one element is picked from each equivalence class. ## Therefore a minimal deterministic automaton is the automaton  ## Example 3.24 Let M be the deterministic automaton  The unmarked pairs in step 1 are The unmarked pairs in the first use of step 2 are The unmarked pairs in the first use of step 2 are The unmarked pairs in the first use of step 2 are The second use of step 2 produces no new results so the equivalence classes are…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{each equivalence class. \#\# Therefore a minimal deterministic automaton is the automaton  \#\# Example 3.24 Let M be the deterministic automaton 
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 81. ph-90c4ef168412ba253b5f — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
is minimized version of the arbitrary automaton recognizing the language L is virtually identical with the intrinsic automaton of the language. Theorem 3.5 For a given regular language L, the two minimal reduced automaton developed above accepting language L are isomorphic. Proof M = ( /Sigma1 , Q , s 0 , ϒ ′ , F ), the minimal reduced automaton developed by the collapsing method is isomorphic to the intrinsic minimal automaton. So Mi = ( /Sigma1 , Qi , [1] , ϒ i , Fi ). Define f : Q → Qi by Assume [ x ] = …
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{is minimized version of the arbitrary automaton recognizing the language L is virtually identical with the intrinsic automaton of the language. Theorem 3.5 For a given regular language L, the two minimal reduced automaton developed above accepting language L are isomorphic. Proo…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 82. ph-96aef37dc15089b8db3d — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
bitrary automaton recognizing the language L is virtually identical with the intrinsic automaton of the language. Theorem 3.5 For a given regular language L, the two minimal reduced automaton developed above accepting language L are isomorphic. Proof M = ( /Sigma1 , Q , s 0 , ϒ ′ , F ), the minimal reduced automaton developed by the collapsing method is isomorphic to the intrinsic minimal automaton. So Mi = ( /Sigma1 , Qi , [1] , ϒ i , Fi ). Define f : Q → Qi by Assume [ x ] = [ y ], then ϒ ( x , u ) ∈ F if…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{bitrary automaton recognizing the language L is virtually identical with the intrinsic automaton of the language. Theorem 3.5 For a given regular language L, the two minimal reduced automaton developed above accepting language L are isomorphic. Proof M = ( /Sigma1 , Q , s 0 , ϒ …}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 83. ph-9178717f3c2ff7e467d0 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
the language L is virtually identical with the intrinsic automaton of the language. Theorem 3.5 For a given regular language L, the two minimal reduced automaton developed above accepting language L are isomorphic. Proof M = ( /Sigma1 , Q , s 0 , ϒ ′ , F ), the minimal reduced automaton developed by the collapsing method is isomorphic to the intrinsic minimal automaton. So Mi = ( /Sigma1 , Qi , [1] , ϒ i , Fi ). Define f : Q → Qi by Assume [ x ] = [ y ], then ϒ ( x , u ) ∈ F if and only if ϒ ( y , u ) ∈ F f…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{the language L is virtually identical with the intrinsic automaton of the language. Theorem 3.5 For a given regular language L, the two minimal reduced automaton developed above accepting language L are isomorphic. Proof M = ( /Sigma1 , Q , s 0 , ϒ ′ , F ), the minimal reduced a…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 84. ph-a150cd5430af176eae7c — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
u ) ∈ F for u , v ∈ /Sigma1 ∗ . Let f ([ x ]) = [ w ] and f ([ y ]) = ([ w ′ ]). Then w u ∈ L if and only if w ′ u ∈ L ( = Fi ). Hence [ w ] = [ w ′ ] and f is well defined. Conversely, assume f ([ x ]) = f ([ y ]) then w u ∈ L if and only if w ′ u ∈ L ( = Fi ) where ϒ ( s 0 , w ) = x and ϒ ( s 0 , w ′ ) = y . Hence ϒ ( x , u ) ∈ F if and only if ϒ ( y , u ) ∈ F and [ x ] = [ y ]. Hence f is well defined and one-to-one. Finally we must show that f ( ϒ ′ ([ x ] , a )) = ϒ i ( f ([ x ]) , a ), Let w ∈ f ([ x ] , then ϒ ( s 0 , w ) = x fo…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{u ) ∈ F for u , v ∈ /Sigma1 ∗ . Let f ([ x ]) = [ w ] and f ([ y ]) = ([ w ′ ]). Then w u ∈ L if and only if w ′ u ∈ L ( = Fi ). Hence [ w ] = [ w ′ ] and f is well defined. Conversely, assume f ([ x ]) = f ([ y ]) then w u ∈ L if and only if w ′ u ∈ L ( = Fi ) where ϒ ( s 0 , w…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 85. ph-92cf1fb211c4069f5c44 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
. Let f ([ x ]) = [ w ] and f ([ y ]) = ([ w ′ ]). Then w u ∈ L if and only if w ′ u ∈ L ( = Fi ). Hence [ w ] = [ w ′ ] and f is well defined. Conversely, assume f ([ x ]) = f ([ y ]) then w u ∈ L if and only if w ′ u ∈ L ( = Fi ) where ϒ ( s 0 , w ) = x and ϒ ( s 0 , w ′ ) = y . Hence ϒ ( x , u ) ∈ F if and only if ϒ ( y , u ) ∈ F and [ x ] = [ y ]. Hence f is well defined and one-to-one. Finally we must show that f ( ϒ ′ ([ x ] , a )) = ϒ i ( f ([ x ]) , a ), Let w ∈ f ([ x ] , then ϒ ( s 0 , w ) = x for x ∈ [ x ]. Let Let w ∈ f ([ x ] , then ϒ ( s 0 , w ) = x for x ∈ [ x ]. Let Let w ∈ f ([ x ] , then ϒ ( s 0 , w ) = x for x ∈ [ x ]. Let and [ y ] = ϒ ′ ([ x ]] , a ) . Now ϒ ( s 0 , w a ) = y , so Let w ∈ f ([ x ] , then ϒ ( s 0 , w ) = x for x ∈ [ x ]. Let and [ y ] = ϒ ′ ([ x ]] , a ) . Now ϒ ( s 0 , w a ) = y , so Let w ∈ f ([ x ] , then ϒ ( s 0 , w ) = x for x ∈ [ x ]. Let and [ y ] = ϒ ′ ([ x ]] , a ) . Now ϒ ( s 0 , w a ) = y , so and so f ( ϒ ′ ([ x ] , a )) = ϒ i ( f ([ x ]) , a ). /square Corollary 3.1 …
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{]) then w u ∈ L if and only if w ′ u ∈ L ( = Fi ) where ϒ ( s 0 , w ) = x and ϒ ( s 0 , w ′ ) = y . Hence ϒ ( x , u ) ∈ F if and only if ϒ ( y , u ) ∈ F and [ x ] = [ y ]. Hence f is well defined and one-to-one. Finally we must show that f ( ϒ ′ ([ x ] , a )) = ϒ i ( f ([ x ]) ,…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 88. ph-2dd3340f90ea9a5fdbba — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
] = ϒ ′ ([ x ]] , a ) . Now ϒ ( s 0 , w a ) = y , so and so f ( ϒ ′ ([ x ] , a )) = ϒ i ( f ([ x ]) , a ). /square Corollary 3.1 For a given regular language, all reduced automata which accept that language are unique up to isomorphism. Instead of looking at the syntactic monoid from the intrinsic point of view, as defined above we examine it using an automaton. In particular we look at minimal automata. The transformation monoid of a deterministic automaton is the image of a homomorphism ϕ from /Sigma1 ∗ to a submonoid TM of the monoi…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{] = ϒ ′ ([ x ]] , a ) . Now ϒ ( s 0 , w a ) = y , so and so f ( ϒ ′ ([ x ] , a )) = ϒ i ( f ([ x ]) , a ). /square Corollary 3.1 For a given regular language, all reduced automata which accept that language are unique up to isomorphism. Instead of lo…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 89. ph-d022934853d0582f7a1c — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
, ¯ a ( si ) = s j if there is an a -arrow from si to s j , i.e. ϒ ( si , a ) = s j . If a , b ∈ /Sigma1 , then ¯ ab = ¯ ab where ¯ ab ( s ) = ¯ a ( b ( s )). More specifically, for u ∈ /Sigma1 ∗ , u ( si ) = s j Thus and if ( si , u ) /turnstileleft ∗ ( s j , λ ). In other words, if the machine is in state si and reads u , then it is in state s j . Let M be the automaton  For convenience, permutation notation is used here although the functions ar…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{, ¯ a ( si ) = s j if there is an a -arrow from si to s j , i.e. ϒ ( si , a ) = s j . If a , b ∈ /Sigma1 , then ¯ ab = ¯ ab where ¯ ab ( s ) = ¯ a ( b ( s )). More specifically, for u ∈ /Sigma1 ∗ , u ( si ) = s j Thus and if ( si , u ) /turnstileleft ∗ ( s j , λ ). In other word…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 90. ph-0fbba7942c206b2d1909 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
for u ∈ /Sigma1 ∗ , u ( si ) = s j Thus and if ( si , u ) /turnstileleft ∗ ( s j , λ ). In other words, if the machine is in state si and reads u , then it is in state s j . Let M be the automaton  For convenience, permutation notation is used here although the functions are not usually permutations, since they are not one-to-one. Thus we have which we shall shorten to Bydefinition let ¯ λ =…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{for u ∈ /Sigma1 ∗ , u ( si ) = s j Thus and if ( si , u ) /turnstileleft ∗ ( s j , λ ). In other words, if the machine is in state si and reads u , then it is in state s j . Let M be the automaton 
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 91. ph-77f81205d116f419e495 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
) /turnstileleft ∗ ( s j , λ ). In other words, if the machine is in state si and reads u , then it is in state s j . Let M be the automaton  For convenience, permutation notation is used here although the functions are not usually permutations, since they are not one-to-one. Thus we have which we shall shorten to Bydefinition let ¯ λ = ( 0 1 2 3 0 1 2 3 ) . We now perform the following prod…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{) /turnstileleft ∗ ( s j , λ ). In other words, if the machine is in state si and reads u , then it is in state s j . Let M be the automaton  For convenience, permutation notation is used here although the functions are not usually permutations, since they are not one-to-one. Thus we have which we shall shorten to Bydefinition let ¯ λ = ( 0 1 2 3 0 1 2 3 ) . We now perform the following prod…
\end{verbatim}
```
92. ph-8b399549d1197584e5a8 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
j . Let M be the automaton  For convenience, permutation notation is used here although the functions are not usually permutations, since they are not one-to-one. Thus we have which we shall shorten to Bydefinition let ¯ λ = ( 0 1 2 3 0 1 2 3 ) . We now perform the following products: For convenience, permutation notation is used here although the functions are not usually permutations, …}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling $ / $$)
$$\text{!-- formula-not-decoded --> For convenience, permutation notation is used here although the functions are not usually permutations, since they are not one-to-one. Thus we have which we shall shorten to Bydefinition let ¯ …}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 98. ph-35a826ebd134437a594a — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
or convenience, permutation notation is used here although the functions are not usually permutations, since they are not one-to-one. Thus we have which we shall shorten to Bydefinition let ¯ λ = ( 0 1 2 3 0 1 2 3 ) . We now perform the following products: then Continuing this process and letting γ = ¯ ab , …
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{or convenience, permutation notation is used here although the functions are not usually permutations, since they are not one-to-one. Thus we have which we shall shorten to Bydefinition let ¯ λ = ( 0 1 2 3 0 1 2 3 ) . We …}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 99. ph-846780b39454786a309e — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
tation is used here although the functions are not usually permutations, since they are not one-to-one. Thus we have which we shall shorten to Bydefinition let ¯ λ = ( 0 1 2 3 0 1 2 3 ) . We now perform the following products: then Continuing this process and letting γ = ¯ ab , δ = ¯ a ¯ a , ε = ¯ b ¯ b , an…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{tation is used here although the functions are not usually permutations, since they are not one-to-one. Thus we have which we shall shorten to Bydefinition let ¯ λ = ( 0 1 2 3 0 1 2 3 ) . We now perform the following prod…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 100. ph-73683672808840fbdcf8 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
b | γ | δ | ε | ζ | | ¯ a | ¯ a | δ | γ | γ | γ | γ | γ | | b | b | ζ | ε | ε | ε | ε | ε | | γ | γ | γ | γ | ε | γ | γ | γ | | δ | δ | γ | γ | γ | γ | γ | γ | | ε | ε | ε | ε | ε | ε | ε | ε | | ζ | ζ | ε | ε | ε | ε | γ | γ | Example 3.25 Let M be the automaton  The table for the transformation monoid TM is seen to be | | λ | ¯ a | b | γ | δ | ε | ζ | η | θ | ϑ | ι | κ | µ | |-----|-----|-------|-----|-----|-----|----…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{b | γ | δ | ε | ζ | | ¯ a | ¯ a | δ | γ | γ | γ | γ | γ | | b | b | ζ | ε | ε | ε | ε | ε | | γ | γ | γ | γ | ε | γ | γ | γ | | δ | δ | γ | γ | γ | γ | γ | γ | | ε | ε | ε | ε | ε | ε | ε | ε | | ζ | ζ | ε | ε | ε | ε | γ | γ | Example 3.25 Let M be the automaton 
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 101. ph-578c00a782ef90c946b0 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
| ¯ a | ¯ a | δ | γ | γ | γ | γ | γ | | b | b | ζ | ε | ε | ε | ε | ε | | γ | γ | γ | γ | ε | γ | γ | γ | | δ | δ | γ | γ | γ | γ | γ | γ | | ε | ε | ε | ε | ε | ε | ε | ε | | ζ | ζ | ε | ε | ε | ε | γ | γ | Example 3.25 Let M be the automaton  The table for the transformation monoid TM is seen to be | | λ | ¯ a | b | γ | δ | ε | ζ | η | θ | ϑ | ι | κ | µ | |-----|-----|-------|-----|-----|-----|-----|-----|-----|-----|…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{| ¯ a | ¯ a | δ | γ | γ | γ | γ | γ | | b | b | ζ | ε | ε | ε | ε | ε | | γ | γ | γ | γ | ε | γ | γ | γ | | δ | δ | γ | γ | γ | γ | γ | γ | | ε | ε | ε | ε | ε | ε | ε | ε | | ζ | ζ | ε | ε | ε | ε | γ | γ | Example 3.25 Let M be the automaton 
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 102. ph-7d649b81d16d9d9693ff — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
here exists u , v, w ∈ /Sigma1 ∗ , v /negationslash= λ such that z = u vw and u v k w ∈ L for all k ≥ 0 . The length of the string u w is less than or equal to n. Further if M is an automaton accepting the language L and M has q states, then n < q. It is possible to have the stronger statement that z = u vw where the length of u v is less than or equal to q. Proof Let L be accepted by the automaton M = ( /Sigma1 , Q , s 0 , ϒ, F ). Let ϒ ( si , ai ) = si + 1 for i = r to t ; denote this by Since L contains a word of length m , where m > q , say w = a 1 a 2 a…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{here exists u , v, w ∈ /Sigma1 ∗ , v /negationslash= λ such that z = u vw and u v k w ∈ L for all k ≥ 0 . The length of the string u w is less than or equal to n. Further if M is an automaton accepting the language L and M has q states, then n \< q. It is possible to have the …}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 103. ph-f5357ac6d31806095236 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
+ 1 for i = r to t ; denote this by Since L contains a word of length m , where m > q , say w = a 1 a 2 a 3 . . . am . Note that if ( s 1 , a 1 a 2 a 3 . . . am ) /turnstileleft ∗ ( sm , λ ), then sm is an acceptance state. Since m > q , in reading w , M must pass through the same state twice. Therefore ( s 1 , a 1 a 2 a 3 . . . aj -1 ) /turnstileleft ∗ ( sk , λ ) and ( s 1 , a 1 a 2 a 3 . . . ak -1 ) /turnstileleft ∗ ( sk , λ ) = for some j < k and both Thus Also ( s j , aj a j + 2 . . . ak -1 ) /…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{+ 1 for i = r to t ; denote this by Since L contains a word of length m , where m \> q , say w = a 1 a 2 a 3 . . . am . Note that if ( s 1 , a 1 a 2 a 3 . . . am ) /turnstileleft ∗ ( sm , λ ), then sm is an acceptance state. Since m \> q , in rea…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 104. ph-54df7a133911093aa0b5 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
Since L contains a word of length m , where m > q , say w = a 1 a 2 a 3 . . . am . Note that if ( s 1 , a 1 a 2 a 3 . . . am ) /turnstileleft ∗ ( sm , λ ), then sm is an acceptance state. Since m > q , in reading w , M must pass through the same state twice. Therefore ( s 1 , a 1 a 2 a 3 . . . aj -1 ) /turnstileleft ∗ ( sk , λ ) and ( s 1 , a 1 a 2 a 3 . . . ak -1 ) /turnstileleft ∗ ( sk , λ ) = for some j < k and both Thus Also ( s j , aj a j + 2 . . . ak -1 ) /turnstileleft ∗ s j , so in reading …
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{ Since L contains a word of length m , where m \> q , say w = a 1 a 2 a 3 . . . am . Note that if ( s 1 , a 1 a 2 a 3 . . . am ) /turnstileleft ∗ ( sm , λ ), then sm is an acceptance state. Since m \> q , in reading w , M must pass through the sam…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 105. ph-519dbc51c7590a1e7c49 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
urnstileleft ∗ ( sm , λ ), then sm is an acceptance state. Since m > q , in reading w , M must pass through the same state twice. Therefore ( s 1 , a 1 a 2 a 3 . . . aj -1 ) /turnstileleft ∗ ( sk , λ ) and ( s 1 , a 1 a 2 a 3 . . . ak -1 ) /turnstileleft ∗ ( sk , λ ) = for some j < k and both Thus Also ( s j , aj a j + 2 . . . ak -1 ) /turnstileleft ∗ s j , so in reading aj a j + 2 . . . ak -1 , M returns to the same state and Letting u = a 1 a 2 . . . aj -1 , v = aj a j + 2 . . . ak -1, and w = akak …
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{urnstileleft ∗ ( sm , λ ), then sm is an acceptance state. Since m \> q , in reading w , M must pass through the same state twice. Therefore ( s 1 , a 1 a 2 a 3 . . . aj -1 ) /turnstileleft ∗ ( sk , λ ) and ( s 1 , a 1 a 2 a 3 . . . ak -1 ) /turnstileleft ∗ ( sk , λ ) = for so…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 106. ph-8e7d4b70772c6b833b0e — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
k b m = a m + k b m ∈ L , which is a contradiction. Second, u = a m , v = b k , and w = b m -k . Byasimilarargument,wereachacontradiction.Third u = a m -k , v = a k b r , and w = b m -r . But then a m -k a k b r a k b r b m -r ∈ L , which is a contradiction. Hence L is not regular. /square ## Exercises For each of the following sets, determine if the set is regular. If it is, describe the set with a regular expression. If it is not a regular set, use the Pumping lemma to show that it is not. - (2) { a n b 2 n a n : n ≥ 1 } . (3) { ( ab ) n : n ≥ 1 } . (4) { a n b …
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{k b m = a m + k b m ∈ L , which is a contradiction. Second, u = a m , v = b k , and w = b m -k . Byasimilarargument,wereachacontradiction.Third u = a m -k , v = a k b r , and w = b m -r . But then a m -k a k b r a k b r b m -r ∈ L , which is a contradiction. Hence L is not regul…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 107. ph-9e2bca12c765fbc26ef9 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
e length is greater than n and less than 2 n. Proof First assume L is infinite. By the Pumping Lemma there exists u v m w ∈ L for all m ≥ 0. Further if M is an automaton accepting the language L and M has n states, then | u w | , the length of the string u w , is less than or equal to n . Assume that after u is read, the machine is in state s . If while reading v , the machine returns to s , let v ′ be the string that is read when the machine first returns to s and v ′ x = v . Thus if we have replace it with Thus M reads the string s 0…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{e length is greater than n and less than 2 n. Proof First assume L is infinite. By the Pumping Lemma there exists u v m w ∈ L for all m ≥ 0. Further if M is an automaton accepting the language L and M has n states, then | u w | , the length of the string u w , is less than or eq…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 108. ph-50d1c9a5fc728dbf1590 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
less than 2 n. Proof First assume L is infinite. By the Pumping Lemma there exists u v m w ∈ L for all m ≥ 0. Further if M is an automaton accepting the language L and M has n states, then | u w | , the length of the string u w , is less than or equal to n . Assume that after u is read, the machine is in state s . If while reading v , the machine returns to s , let v ′ be the string that is read when the machine first returns to s and v ′ x = v . Thus if we have replace it with Thus M reads the string s 0 , u ( v ′ ) n w for any nonneg…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{less than 2 n. Proof First assume L is infinite. By the Pumping Lemma there exists u v m w ∈ L for all m ≥ 0. Further if M is an automaton accepting the language L and M has n states, then | u w | , the length of the string u w , is less than or equal to n . Assume that after u …}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 109. ph-9921a391d7283eda51a8 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
onstructed. The PDA, beginning at the left, reads a letter at a time in the same manner as a standard automaton. The PDA may read a letter from the tape or pop (remove from the top) and read a symbol from the stack or both. Depending on its current state and the symbol(s) read, the PDA may change state, push a symbol in the stack, or both.  We now define a PDA more formally. ## Definition 3.8 A pushdown automaton is a sextuple ## Definition 3.8 A pushdown automaton is a sextuple ## Definition 3.8 A pushdown automaton is a sextuple where /Sigma1 is a finite alphabet, Q is a finite set of states, s is the i…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{nner as a standard automaton. The PDA may read a letter from the tape or pop (remove from the top) and read a symbol from the stack or both. Depending on its current state and the symbol(s) read, the PDA may change state, push a symbol in the stack, or both. 
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 111. ph-6d07c4d5a7ba529cc8dc — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
Image](./AutomataTheory_artifacts/image_000112_b968bb9607a88ba814f66590a1b105c8356ddd63139d322652c16e02b93f6004.png) We now define a PDA more formally. ## Definition 3.8 A pushdown automaton is a sextuple where /Sigma1 is a finite alphabet, Q is a finite set of states, s is the initial or starting state, I is a finite of stack symbols, ϒ is the transition relation and F is the set of acceptance states. The relation ϒ is a subset of Thus the relation reads a letter from /Sigma1 λ , determines the state, and …
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{Image](./AutomataTheory\_artifacts/image\_000112\_b968bb9607a88ba814f66590a1b105c8356ddd63139d322652c16e02b93f6004.png) We now define a PDA more formally. \#\# Definition 3.8 A pushdown automaton is a sextuple where /Sigma1 is…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 112. ph-07948fe2ba33949366c7 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
t reads the language L = { w c w r : w ∈ { a , b } ∗ } . - (20) Let /Sigma1 = { a , b } . Construct a pushdown automaton that reads the language L = { w : The number of a s in w is equal to twice the number of b s or the number of b s in w is equal to three times the number of a s } . - (19) Let /Sigma1 = { a , b , c } . Construct a pushdown automaton that reads the language L = { w : The number of a s in w is equal to the sum of the number of b s and c s } . - (21) Given two pushdown automata over the same alphabet /Sigma1 and accepti…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{t reads the language L = \{ w c w r : w ∈ \{ a , b \} ∗ \} . - (20) Let /Sigma1 = \{ a , b \} . Construct a pushdown automaton that reads the language L = \{ w : The number of a s in w is equal to twice the number of b s or the number of b s in w is equal to three times the number of a…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 113. ph-ff60eb4a33f2aa44e9d1 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
w r : w ∈ { a , b } ∗ } . - (20) Let /Sigma1 = { a , b } . Construct a pushdown automaton that reads the language L = { w : The number of a s in w is equal to twice the number of b s or the number of b s in w is equal to three times the number of a s } . - (19) Let /Sigma1 = { a , b , c } . Construct a pushdown automaton that reads the language L = { w : The number of a s in w is equal to the sum of the number of b s and c s } . - (21) Given two pushdown automata over the same alphabet /Sigma1 and accepting languages L and L ′ respecti…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{w r : w ∈ \{ a , b \} ∗ \} . - (20) Let /Sigma1 = \{ a , b \} . Construct a pushdown automaton that reads the language L = \{ w : The number of a s in w is equal to twice the number of b s or the number of b s in w is equal to three times the number of a s \} . - (19) Let /Sigma1 = \{ a…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 114. ph-224e5ae41948519d48a3 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
automata over the same alphabet /Sigma1 and accepting languages L and L ′ respectively, - (a) Describe how to construct a pushdown automaton /Gamma1 1 that accepts the language L ∪ L ′ . - (b) Construct a pushdown automaton /Gamma1 1 that accepts the language L ∪ L ′ where L is the language accepted by the automaton in Example 3.26 and L ′ is the language accepted by the automaton in Example 3.27. - (22) Given two pushdown automata over the same alphabet /Sigma1 and accepting la…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{automata over the same alphabet /Sigma1 and accepting languages L and L ′ respectively, - (a) Describe how to construct a pushdown automaton /Gamma1 1 that accepts the language L ∪ L ′ . - (b) Construct a pushdown automat…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 115. ph-a0fda5f83f6270e04c92 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
coded --> over the same alphabet /Sigma1 and accepting languages L and L ′ respectively, - (a) Describe how to construct a pushdown automaton /Gamma1 1 that accepts the language L ∪ L ′ . - (b) Construct a pushdown automaton /Gamma1 1 that accepts the language L ∪ L ′ where L is the language accepted by the automaton in Example 3.26 and L ′ is the language accepted by the automaton in Example 3.27. - (22) Given two pushdown automata over the same alphabet /Sigma1 and accepting languages L and L ′ respective…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{coded --> over the same alphabet /Sigma1 and accepting languages L and L ′ respectively, - (a) Describe how to construct a pushdown automaton /Gamma1 1 that accepts the language L ∪ L ′ . - (b) Construct a pushdown automaton /Gamma1 1 that accepts th…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 116. ph-483db656693ea0f64a32 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
utomaton in Example 3.27 . and and - (23) Given a pushdown automaton /Gamma1 = ( N , ϒ, S , P ) over the alphabet /Sigma1 and accepting language L , 2. (a) Describe how to construct a pushdown automaton /Gamma1 3 which accepts the language L ∗ . 3. (b) Construct a pushdown automaton /Gamma1 3 that accepts the language L ∪ L ′ where L is the language accepted by the automaton in Example 3.26 and L ′ is the language accepted by the automaton in Example 3.27 . - (24) Given two pushdown automata over the same alphabet /Sigma1 and accepting…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{utomaton in Example 3.27 . and and - (23) Given a pushdown automaton /Gamma1 = ( N , ϒ, S , P ) over the alphabet /Sigma1 and accepting language L , 2. (a) Describe how to construct a pushdown automaton /Gamma1 3 which accepts the language L ∗ . 3. (b) Construct a pushdown autom…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 117. ph-ad2aa4800f2b66d749ce — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
d and - (23) Given a pushdown automaton /Gamma1 = ( N , ϒ, S , P ) over the alphabet /Sigma1 and accepting language L , 2. (a) Describe how to construct a pushdown automaton /Gamma1 3 which accepts the language L ∗ . 3. (b) Construct a pushdown automaton /Gamma1 3 that accepts the language L ∪ L ′ where L is the language accepted by the automaton in Example 3.26 and L ′ is the language accepted by the automaton in Example 3.27 . - (24) Given two pushdown automata over the same alphabet /Sigma1 and accepting languages L and L ′ respecti…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{d and - (23) Given a pushdown automaton /Gamma1 = ( N , ϒ, S , P ) over the alphabet /Sigma1 and accepting language L , 2. (a) Describe how to construct a pushdown automaton /Gamma1 3 which accepts the language L ∗ . 3. (b) Construct a pushdown automaton /Gamma1 3 that accepts t…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 118. ph-ffe7184ba866e7687caa — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
B can be replaced by other symbols while + and the integers cannot be replaced. The symbols that can be replaced by other symbols are called nonterminal symbols and the symbols that can not be replaced by other symbols are called terminal symbols . We generate an element of the language when the string consists only of terminal symbols. The rules which tell us how to replace symbols are called productions . We denote the production (or rule) which tells us that add can be replaced with A + B Thus the productions for our first example above are Thus the productions for our first example above are Thus the productions for our first example above are Below, we shall expand our rules to do arbitrary addition, subtraction, mul…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{symbols that can be replaced by other symbols are called nonterminal symbols and the symbols that can not be replaced by other symbols are called terminal symbols . We generate an element of the language when the string consists only of terminal symbols. The rules which tell us …}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 120. ph-c877bc37e8214f20410a — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
set of nonterminal symbols N, a finite set of terminal symbols /Sigma1 , an element S ∈ N, called the start symbol and a finite set of productions P , which is a relation in ( N ∪ /Sigma1 ) ∗ such that each first element in an ordered pair of P contains a symbol from N and at least one production has S as the left string in some ordered pair. Definition 4.2 If W and W ′ are elements of ( N ∪ /Sigma1 ) ∗ , W = u vw , W ′ = u v ′ w , and v → v ′ is a production, this is denoted by W ⇒ W ′ . If for n ≥ 1 , then Wn is derived from W 1 . This is denoted by W 1 ⇒ ∗ n Wn…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{set of nonterminal symbols N, a finite set of terminal symbols /Sigma1 , an element S ∈ N, called the start symbol and a finite set of productions P , which is a relation in ( N ∪ /Sigma1 ) ∗ such that each first element in an ordered pair of P contains a symbol from N and at le…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 121. ph-d0b9d575f788a477ccf0 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
is denoted by W 1 ⇒ ∗ n Wn and is called a derivation . If the number of productions in not important we simply use W 1 ⇒ ∗ Wn. The set of all strings of elements of /Sigma1 which may be generated by the set of productions P is called the language generated by the grammar /Gamma1 and is denoted by /Gamma1 ( L ) . To generate a word from the grammar /Gamma1 , we keep using productions to derive new strings until we have a string consisting only of terminal elements. Thus in our example above, and where we will denote ( add , A + B ) by …
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{is denoted by W 1 ⇒ ∗ n Wn and is called a derivation . If the number of productions in not important we simply use W 1 ⇒ ∗ Wn. The set of all strings of elements of /Sigma1 which may be generated by the set of productions P is called the language generated by the grammar /Gamma…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 122. ph-0ad595ad7b7bab59eb8e — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
alled a derivation . If the number of productions in not important we simply use W 1 ⇒ ∗ Wn. The set of all strings of elements of /Sigma1 which may be generated by the set of productions P is called the language generated by the grammar /Gamma1 and is denoted by /Gamma1 ( L ) . To generate a word from the grammar /Gamma1 , we keep using productions to derive new strings until we have a string consisting only of terminal elements. Thus in our example above, and where we will denote ( add , A + B ) by add → A + B , ( A , A + B ) by A → …
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{alled a derivation . If the number of productions in not important we simply use W 1 ⇒ ∗ Wn. The set of all strings of elements of /Sigma1 which may be generated by the set of productions P is called the language generated by the grammar /Gamma1 and is denoted by /Gamma1 ( L ) .…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 123. ph-533066d00d9762695439 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
derive new strings until we have a string consisting only of terminal elements. Thus in our example above, and where we will denote ( add , A + B ) by add → A + B , ( A , A + B ) by A → A + B , etc. If we eliminate the production ( B , A × B ), the language generated by /Gamma1 is the set of all formal expressions of finite sums of nonnegative integers less than 10. Example 4.1 In the grammar described above, derive the expression and where we will denote ( add , A + B ) by add → A + B , ( A , A + B ) by A → A + B , etc. If we eliminate the pr…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling $ / $$)
$$\text{a-not-decoded --> and where we will denote ( add , A + B ) by add → A + B , ( A , A + B ) by A → A + B , etc. If we eliminate the production ( B , A × B ), the language generated by /Gamma1 is the set of all formal expressions of finite sums of nonne…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 128. ph-689ca072626842b767dd — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
ormula-not-decoded --> where we will denote ( add , A + B ) by add → A + B , ( A , A + B ) by A → A + B , etc. If we eliminate the production ( B , A × B ), the language generated by /Gamma1 is the set of all formal expressions of finite sums of nonnegative integers less than 10. Example 4.1 In the grammar described above, derive the expression Begin with the production to derive Then use the …
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{ormula-not-decoded --> where we will denote ( add , A + B ) by add → A + B , ( A , A + B ) by A → A + B , etc. If we eliminate the production ( B , A × B ), the language generated by /Gamma1 is the set of all formal expressions of finite sums of nonnegative integers less than 10…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 129. ph-cab931aff6db37cb08b4 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
we will denote ( add , A + B ) by add → A + B , ( A , A + B ) by A → A + B , etc. If we eliminate the production ( B , A × B ), the language generated by /Gamma1 is the set of all formal expressions of finite sums of nonnegative integers less than 10. Example 4.1 In the grammar described above, derive the expression Begin with the production to derive Then use the production to derive Then use…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{we will denote ( add , A + B ) by add → A + B , ( A , A + B ) by A → A + B , etc. If we eliminate the production ( B , A × B ), the language generated by /Gamma1 is the set of all formal expressions of finite sums of nonnegative integers less than 10. Example 4.1 In the grammar …}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 130. ph-fa9f1315c531fee6e513 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
s the set of all formal expressions of finite sums of nonnegative integers less than 10. Example 4.1 In the grammar described above, derive the expression Begin with the production to derive Then use the production to derive Then use the production to derive Then use the productions to derive 2 + 4 + 7 × 6. Note that we cannot derive Ex…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{s the set of all formal expressions of finite sums of nonnegative integers less than 10. Example 4.1 In the grammar described above, derive the expression Begin with the production to derive Then use the production to derive Then use the production to derive Then use the productions to derive 2 + 4 + 7 × 6. Note that we cannot derive Ex…
\end{verbatim}
```
131. ph-e963af01dadab966971c — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
n 10. Example 4.1 In the grammar described above, derive the expression Begin with the production to derive Then use the production to derive Then use the production to derive Then use the productions to derive 2 + 4 + 7 × 6. Note that we cannot derive Example 4.2 Suppose we want a grammar which derives arithmetic expressions for the se…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{n 10. Example 4.1 In the grammar described above, derive the expression Begi…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 132. ph-906faee4813d170504c0 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
7 , 8 , 9 } . Thus the language generated by the grammar is the set of all finite arithmetic expressions for the set of integers { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 } . Examples would be 3 × (5 + 4) and (4 + 5) ÷ (3ˆ2), where ˆ denotes exponent. As mentioned above, we obviously want to exclude expressions such as 3 +× 6 and 3 +÷ 6 × 4 -5 . Let the set N = { S , A , B } and /Sigma1 = {+ , -, × , ÷ , ˆ , 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , ( , ) } . Wewill need the following productions: We will use the grammar to derive the arithmetic expression We will use the grammar to derive the arithmetic expression We will use the grammar to derive the arithmetic expression We begin with the production We will use the grammar to derive the arithmetic expression We begin with the production We will use the grammar to derive the arithmetic expression We begin with the production We will use the grammar to derive the arithmetic expression We begin with the production We will use the grammar to derive the arithmetic expression We begin with the production We then use the pro…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{would be 3 × (5 + 4) and (4 + 5) ÷ (3ˆ2), where ˆ denotes exponent. As mentioned above, we obviously want to exclude expressions such as 3 +× 6 and 3 +÷ 6 × 4 -5 . Let the set N = \{ S , A , B \} and /Sigma1 = \{+ , -, × , ÷ , ˆ , 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , ( , ) \} . W…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 136. ph-64caf21c08969db601d3 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
5) ÷ (3ˆ2), where ˆ denotes exponent. As mentioned above, we obviously want to exclude expressions such as 3 +× 6 and 3 +÷ 6 × 4 -5 . Let the set N = { S , A , B } and /Sigma1 = {+ , -, × , ÷ , ˆ , 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , ( , ) } . Wewill need the following productions: We will use the grammar to derive the arithmetic expression We begin with the production We then use the productions and to derive The pro…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{5) ÷ (3ˆ2), where ˆ denotes exponent. As mentioned above, we obviously want to exclude expressions such as 3 +× 6 and 3 +÷ 6 × 4 -5 . Let the set N = \{ S , A , B \} and /Sigma1 = \{+ , -, × , ÷ , ˆ , 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , ( , ) \} . Wewill need the following produ…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 137. ph-d351611f5d38b38f875c — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
xponent. As mentioned above, we obviously want to exclude expressions such as 3 +× 6 and 3 +÷ 6 × 4 -5 . Let the set N = { S , A , B } and /Sigma1 = {+ , -, × , ÷ , ˆ , 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , ( , ) } . Wewill need the following productions: We will use the grammar to derive the arithmetic expression We begin with the production We then use the productions and to derive The productions give us to derive to…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{xponent. As mentioned above, we obviously want to exclude expressions such as 3 +× 6 and 3 +÷ 6 × 4 -5 . Let the set N = \{ S , A , B \} and /Sigma1 = \{+ , -, × , ÷ , ˆ , 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , ( , ) \} . Wewill need the following productions: We will use the grammar to derive the arithmetic expression We begin with the production We then use the productions and to derive The productions give us to derive to…
\end{verbatim}
```
138. ph-9d4fe3ac807f08bb2f5d — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
1 = {+ , -, × , ÷ , ˆ , 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , ( , ) } . Wewill need the following productions: We will use the grammar to derive the arithmetic expression We begin with the production We then use the productions and to derive The productions give us to derive to derive The productions give us Finally we use the productions We will use the grammar to derive the arithmetic expression We begin with the production We will use the grammar to derive the arithmetic expression We begin with the production We then use the productions and to derive The productions give us to derive to derive The productions give us Finally we use the productions We will use the grammar to derive the arithmetic expression We begin with the production We then use the productions and to derive The productions give us to derive to derive The productions give us Finally we use the productions We will use the grammar to derive the arithmetic expression We begin with the production We will use the grammar to derive the arithmetic expression We begin with the production We then use the productions and to derive The productions give us to derive to derive The productions give us Finally we use the productions We will use the grammar to derive the arithmetic expression We begin with the production We then use the productions and to derive The productions give us to derive to derive The productions give us Finally we use the productions We next use the grammar to derive the arithmetic expressio…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{llowing productions: We will use the grammar to derive the arithmetic expression We begin with the production We will use the grammar to derive the arithmetic expression We begin with the production We then use the productions and to derive The productions give us to derive to derive The productions give us Finally we use the productions We next use the grammar to derive the arithmetic expressio…
\end{verbatim}
```
141. ph-d096f66082c5d70bac52 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
mula-not-decoded --> We will use the grammar to derive the arithmetic expression We begin with the production We then use the productions and to derive The productions give us to derive to derive The productions give us Finally we use the productions We next use the grammar to derive the arithmetic expression We will use the grammar to derive the arithmetic expression We begin with the production We then use the producti…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling $ / $$)
$$\text{mula-not-decoded --> We begin with the production We then use the productions and to derive The productions give us to derive to derive The productions give us <!-…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 143. ph-1bfb1e05c581f57fc13c — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
mula-not-decoded --> We then use the productions and to derive The productions give us to derive to derive The productions give us Finally we use the productions We next use the grammar to derive the arithmetic expression We begin with the production We then use the productions <…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{mula-not-decoded --> We then use the productions and to derive The productions give us to derive to derive The productions give us Fin…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 144. ph-3a6a5714254a67ae67b7 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
rmula-not-decoded --> We then use the productions and to derive The productions give us to derive to derive The productions give us Finally we use the productions We next use the grammar to derive the arithmetic expression We begin with the production We then use the productions …
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{rmula-not-decoded --> We then use the productions and to derive The productions give us to derive to derive The productions give us Finally we use the productions …}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 145. ph-5aa1d5eb7cd3e77983a6 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
rmula-not-decoded --> We then use the productions and to derive The productions give us to derive to derive The productions give us Finally we use the productions We next use the grammar to derive the arithmetic expression We begin with the production We then use the productions Finally we use the production…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{rmula-not-decoded --> We then use the productions and to derive The productions give us to derive to derive The productions give us Finally we use the productions …}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 146. ph-dbb986f185b5ac3cf484 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
use the productions and to derive The productions give us to derive to derive The productions give us Finally we use the productions We next use the grammar to derive the arithmetic expression We begin with the production We then use the productions Finally we use the productions …
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{use the productions and to derive The productions give us to derive to derive The productions give us Finally we use the productions We next use the grammar to der…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 147. ph-164f2837f74dc029dc05 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
erive The productions give us to derive to derive The productions give us Finally we use the productions We next use the grammar to derive the arithmetic expression We begin with the production We then use the productions Finally we use the productions Finally we use the productions We next use the grammar to derive the arithmetic expressio…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling $ / $$)
$$\text{ctions give us Finally we use the productions We next use the grammar to derive the arithmetic expression We begin with the production…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 149. ph-2af1a6713c03f50c1b8a — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
ot-decoded --> Finally we use the productions We next use the grammar to derive the arithmetic expression We begin with the production We then use the productions Finally we use the productions Example 4.3 In a similar manner, we may form arithmetic expressions in postfix notatio…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{ot-decoded --> Finally we use the productions We next use the grammar to derive the arithmetic expression We begin with the production …}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 150. ph-2a69d7149e4ee3fe3b26 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
grammar to derive the arithmetic expression We begin with the production We then use the productions Finally we use the productions Example 4.3 In a similar manner, we may form arithmetic expressions in postfix notation. Let the set N = { S , A , B } and to derive We will need the following productions: Cons…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{grammar to derive the arithmetic expression We begin with the production We then use the productions Fina…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 151. ph-c7fd2fced5a0cc9a1ab1 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
n with the production We then use the productions Finally we use the productions Example 4.3 In a similar manner, we may form arithmetic expressions in postfix notation. Let the set N = { S , A , B } and to derive We will need the following productions: Consider the expression 3 2 + 4 7 +× . Since our integers are all less than ten, 3 2…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{n with the production We then use the productions Finally we use the productions We then use the productions Finally we use the productions Example 4.3 In a similar manner, we may form arithmetic expressions in postfix notation. Let the set N = { S , A , B } and to derive We will need the following productions: Consider the expression 3 2 + 4 7 +× . Since our integers are all less than ten, 3 2…
\end{verbatim}
```
152. ph-b570cc1bce8a8ffd9459 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
-> Example 4.3 In a similar manner, we may form arithmetic expressions in postfix notation. Let the set N = { S , A , B } and to derive We will need the following productions: Consider the expression 3 2 + 4 7 +× . Since our integers are all less than ten, 3 2 + represents the integer symbol 3, followed by the integer symbol 2 and the + symbol. To construct this expression we begin with the production We then use the productions Example 4.3 In a similar manner, we may form arithmetic expressions in postfix notation. Let the set N = \{ S , A , B \} and to derive We will need the following productions: Consider the exp…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling $ / $$)
$$\text{expressions in postfix notation. Let the set N = \{ S , A , B \} and to derive We will need the following productions: Consider the expression 3 2 + 4 7 +× . Since our integers are all less than ten, 3 2 + represents the in…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 155. ph-d964d23cff70fffba317 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
on. Let the set N = { S , A , B } and to derive We will need the following productions: Consider the expression 3 2 + 4 7 +× . Since our integers are all less than ten, 3 2 + represents the integer symbol 3, followed by the integer symbol 2 and the + symbol. To construct this expression we begin with the production We then use the productions Finally we use the productions to derive We will need the following productions: Consider the expression 3 2 + 4 7 +× . Since our integers are all less than ten, 3 2 + represents the integer symbol 3, followed by t…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling $ / $$)
$$\text{the following productions: Consider the expression 3 2 + 4 7 +× . Since our integers are all less than ten, 3 2 + represents the integer symbol 3, followed by the integer symbol 2 and the + symbol. To construct this expression we begin with the produ…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 158. ph-bde649340b6444770548 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
!-- formula-not-decoded --> Consider the expression 3 2 + 4 7 +× . Since our integers are all less than ten, 3 2 + represents the integer symbol 3, followed by the integer symbol 2 and the + symbol. To construct this expression we begin with the production We then use the productions Finally we use the productions Example 4.4 Agrammar may also be used to derive proper sentences. These sentence…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{!-- formula-not-decoded --> Consider the expression 3 2 + 4 7 +× . Since our integers are all less than ten, 3 2 + represents the integer symbol 3, followed by the integer symbol 2 and the + symbol. To construct this expression we begin with the production Consider the expression 3 2 + 4 7 +× . Since our integers are all less than ten, 3 2 + represents the integer symbol 3, followed by the integer symbol 2 and the + symbol. To construct this expression we begin with the production We then use the productions Finally we use the productions Example 4.4 Agrammar may also be used to derive proper sentences. These sentence…
\end{verbatim}
```
159. ph-45f12d17962feb11797b — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
he fast horse leaped over the old fence. The cowboy rode slowly into the sunset. to derive The productions give us to derive Before actually stating the grammar let us decide upon its structure. This allows us to be assured that each sentence in the grammar is a grammatically correct sentence. Each of our sentences has a noun phrase (noun p), a verb phrase (verb p), and another noun phrase. In addition the last two sentences have a preposition (prep). Therefore let the first production be In our example, the most general form of a noun phrase is an article followe…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{he fast horse leaped over the old fence. The cowboy rode slowly into the sunset. to derive The productions give us to derive Before actually stating the grammar let us decide upon its structure. This allows us to be assured that each sentence in the grammar is a grammatically co…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling 160. ph-3452988dc40c0d37f6a7 — automata/docling_md/AutomataTheory.md
### Plain (markdown context)
upon its structure. This allows us to be assured that each sentence in the grammar is a grammatically correct sentence. Each of our sentences has a noun phrase (noun p), a verb phrase (verb p), and another noun phrase. In addition the last two sentences have a preposition (prep). Therefore let the first production be In our example, the most general form of a noun phrase is an article followed by an adjective and then a noun. Therefore let the next production be where 'art' represents article and 'adj' represents adjective The most gen…
### Rendered (KaTeX / MathJax-style $ / $$)
$$\text{upon its structure. This allows us to be assured that each sentence in the grammar is a grammatically correct sentence. Each of our sentences has a noun phrase (noun p), a verb phrase (verb p), and another noun phrase. In addition the last two sentences have a preposition (prep)…}$$
### Raw LaTeX (paste into a .tex document)
```latex
% Placeholder: formula region was not decoded in the original Docling run.
% Re-run: docling