Why is {a^n a^n | n >= 0} regular?
I understand the reason and the proof why {a^n b^n | n >= 0} is NOT regular.
Why is {a^nb^n | n >= 0} not regular?
The solution of one of my exercises is: {a^n a^n | n >= 0} is regular. How can I prove this thesis?
Yes, Language {an an | n >= 0} is a regular language. To proof that certain language is regular, you can draw its dfa/regular expression. And you can drive do for this language as follows:
Because "anan for n >= 0" is same as "a2n for n >=0", and that is "set of all string contests of even number of symbol a" that is regular — regular expression for this is (aa)*.
Note, regular expressions is only possible for regular languages hence it is proved that {an an | n >= 0} is a regular language. and DFA would be:
I would suggest you to read this why languages like {an bn | n >= 0} are not regular.
- 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