Menu
I'd like to know if the concatenation between two language (one regular and the other not) is always not regular or it may happen that the output is a regular language. Thanks.
209
Concatenation: the concatenation of two regular languages is also a regular language. Complement: the complement of a regular language is also a regular language. "*" Operator: the concatenation of 0 or more strings in a regular language is also a regular language.
Regular languages are closed under union, concatenation, star, and complementation.
(b) Union of a regular language with a disjoint non-regular language cannot be regular. Ans: True. Let L1 is a regular language and L2 is a non−regular language and they are disjoint i.e. L1 ∩ L2 = ∅. Suppose L = L1 ∪ L2 and L is regular (since regular languages are closed under union).
The complement of a nonregular language is never regular. If L is nonregular and Lc were regular, then (Lc)c = L would be regular, a contradiction. Therefore, Lc in your example isn't regular.
No, because we can find a counterexample that prove that sometimes it happen:
L1 not regular: (a^2)^n with n>=0
L2 regular: a*
The concatenation produce the language L3= aa* and this is obviously regular.
168
a^(2^n) n>=0 is non regular except concatenating it with a* which is regular, produces a regular language. It becomes L = {a^(2^n)a*, n>=0} which basically cancels down to L={aa*} which is regular.
Patrick87, (a^2)^n n>1 has regular expression (aaaa)(aa)*
32
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
