Why is $\{a^nb^n \mid n \geq 1\}$ not type 3 (regular)? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-05-24T19:02:40Z https://cs.stackexchange.com/feeds/question/102801 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/102801 0 Why is $\{a^nb^n \mid n \geq 1\}$ not type 3 (regular)? OddDev https://cs.stackexchange.com/users/66977 2019-01-13T12:45:46Z 2019-01-13T21:11:33Z <p>My book states that the language <span class="math-container">$$L_1 = \{a^nb^n\mid n\geq 1\}$$</span> is of type 2 (context-free) but not of type 3 (regular) since there is no regular grammar to produce it. However, I can't really imagine how this grammar should not be applicable or why it shouldn't be a valid type 3 grammar: <span class="math-container">$$S \to aS \mid bS \mid b\,.$$</span></p> <p>For my understanding this grammar produces the language in question and also fulfils the type 3 criteria.</p> https://cs.stackexchange.com/questions/102801/why-is-anbn-mid-n-geq-1-not-type-3-regular/102802#102802 2 Answer by Apass.Jack for Why is $\{a^nb^n \mid n \geq 1\}$ not type 3 (regular)? Apass.Jack https://cs.stackexchange.com/users/91753 2019-01-13T12:54:34Z 2019-01-13T12:54:34Z <p><span class="math-container">$S\Rightarrow bS\Rightarrow baS\Rightarrow bab$</span>.</p> <p>However, <span class="math-container">$bab$</span> is not <span class="math-container">$a^nb^n$</span> for any <span class="math-container">$n$</span>.</p> <hr> <p>(<strong>Exercise.</strong>) Is the following grammar a grammar for <span class="math-container">$L_1$</span>?</p> <p><span class="math-container">$S \to Sa \mid Sb \mid a$</span></p> https://cs.stackexchange.com/questions/102801/why-is-anbn-mid-n-geq-1-not-type-3-regular/102803#102803 1 Answer by David Richerby for Why is $\{a^nb^n \mid n \geq 1\}$ not type 3 (regular)? David Richerby https://cs.stackexchange.com/users/9550 2019-01-13T12:54:44Z 2019-01-13T12:54:44Z <p>Your grammar produces every possible string that ends in&nbsp;<span class="math-container">$b$</span>.</p> <p>The proof that <span class="math-container">$\{a^nb^n\mid n\geq 1\}$</span> is not regular is standard and can be found in any textbook&nbsp;&ndash; use the pumping lemma, Myhill&ndash;Nerode or one of the other characterizations of regular languages.</p>