Finiteness of Regular Language
We all know that (a + b)* is a regular language for containing only symbols a and b.
But (a + b)* is a string of infinite length and it is regular as we can build a finite automata, so it should be finite.
Can anyone please explain this?
Finite automaton can be constructed for any regular language, and regular language can be a finite or an infinite set. Of-course there are infinite sets those are not regular sets. Check the Venn diagram below:
Notes:
1. every finite set is a regular set.
2. any dfa for an infinite set will always contains loop (or dfa without loop is not possible for infinite set).
3. every non-regular language is an infinite set.
The word "finite" in finite automata significance the presence of 'finite amount of memory' in automata for the class of regular languages, hence only 'finite' (or says bounded) amount of information can be stored at any instance of time while processing a string of language.
In finite automata, memory is present in the form of states only (whereas in the other class of automata like Pda, Turing Machines external memory are used to store unbounded information). You can think a finite automata as a CPU without explicit memory; that can only store recent results in its registers.
So, we can define "regular language" as — a class of languages for which only bounded (finite) information is required to stored at any instance of time while processing language strings.
Further read (for infinite languages):
- What is regular language: What is basically a regular language? And Why
a*b*is regular? But language{ anbn | n > 0 }is not a regular language - To understand how states are uses as memory element read this answer: How to write regular expression for a DFA
- And difference between automate for finite ans infinite regular language: To make sure: Pumping lemma for infinite regular languages only?
- Are my DFA's correct? (arbitrary long sequence of 0's and 1's)
- Understanding (and forming) the regular expression of this finite automaton
- Text between two characters
- Regular expression for L = {w|w doesn't contain the substring 110} over the alphabet Σ = {0,1}
- Whether this is the general approach for making a DFA for accepting prefix language of a given regular language?
- Is the language {0^n 1^n 0^k | k != n} context free?
- Automaton that recognizes a language without 3 consecutive zeros
- How to write a generical REGEX expression to: Σ = {a, b, c}, L = {w ∈ Σ ∗ / the first symbol of w is equal to the last symbol of w}?
- How can I allow a single space in a regex in Dart but allow other characters to be 1 or more?
- Which programming languages have a regular grammar?
- Automata theory: Formal definition of indistinguishable & distinguishable strings and example confusion
- Why is {a^n a^n | n >= 0} regular?
- Is this languages REGULAR / CONTEXT FREE but not REG / Nothing?
- Need simple regex (regular expression) for dynamic expression
- Regular expression for [a-zA-Z]
- Regular expression without "Double or more" spaces
- Split a string by punctuation marks (.!?;:) while excluding abbreviations
- How should one proceed to prove (or find) if two regular expressions are same or equivalent?
- Why do we use pumping lemma to prove the non-regularity of languages? WHY?
- Regex to Detect Zalgo
- Regex-How to prevent repeated special characters?
- Closure property of regular languages under concatenation and star operation
- Using string of set length with pumping lemma to prove irregularity
- Why L={wxw^R| w, x belongs to {a,b}^+ } is a regular language
- Regular expression for the following condition
- Checking a string with a regular expression
- Are there any languages such that they are proper subsets of each other and satisfy these conditions
- Given a binary alphabet {0,1}, write a regular expression that recognises all words that have an even number of ’1’s and starts and ends with a ’0’
- Validating a url path with regex and excluding special characters
- Explain regular expression in Python