3 ms·

> Let’s consider a simple problem that finite automata cannot solve: recognizing the language L = {anbn|n ≥ 0}. This language consists of strings with n ’a’s fo

> Let’s consider a simple problem that finite automata cannot solve: recognizing the language L = {anbn|n ≥ 0}. This language consists of strings with n ’a’s followed by n ’b’s. > A regular expression or finite automaton can recognize strings in this language up to a certain length. For example, the regular expression a∗b∗ can recognize strings in L up to length 2. That regex makes no guarantee that the number of a's matches the number of b's, which doesn't match their language definition. I think they wanted (ab)*, which does, and can match any string in their language.

Tainnor 3y ago
Wow, that's wild. Not only are they writing down things everybody in that field should know, but they fail to even properly understand the very basics of regular languages. Literally what you learn in the first week of an intro to CS course. What they wrote makes absolutely no sense, I have no idea where this confusion came from. They're also at least imprecise (or possibly again confused) when they write that "no regular expression [...] can recognize all strings in L" - they should have written "exactly the strings in L", because you can of course write a regex (or FSM) that recognises every string. However, they definitely shouldn't have written (ab)* because this doesn't recognise L either (it does keep the number of as and bs balanced, but they're in the wrong order) - and with good reason, that language is simply not regular: as they do correctly write, it would require arbitrarily large memory (formally, that's the Myhill-Nerode theorem). (Also, as a side-note, it's "an automaton", not "an automata", and the fact that they have no spacing around the | in their set notation is also a minor pet peeve of mine. But now I'm splitting hairs.)

3 ms·

> Let’s consider a simple problem that finite automata cannot solve: recognizing the language L = {anbn|n ≥ 0}. This language consists of strings with n ’a’s fo

by morthaur 3y ago

Tainnor 3y ago
Wow, that's wild. Not only are they writing down things everybody in that field should know, but they fail to even properly understand the very basics of regular languages. Literally what you learn in the first week of an intro to CS course. What they wrote makes absolutely no sense, I have no idea where this confusion came from. They're also at least imprecise (or possibly again confused) when they write that "no regular expression [...] can recognize all strings in L" - they should have written "exactly the strings in L", because you can of course write a regex (or FSM) that recognises every string. However, they definitely shouldn't have written (ab)* because this doesn't recognise L either (it does keep the number of as and bs balanced, but they're in the wrong order) - and with good reason, that language is simply not regular: as they do correctly write, it would require arbitrarily large memory (formally, that's the Myhill-Nerode theorem). (Also, as a side-note, it's "an automaton", not "an automata", and the fact that they have no spacing around the | in their set notation is also a minor pet peeve of mine. But now I'm splitting hairs.)