Question: Recall that for any two regular languages L _ ( 1 ) , L _ ( 2 ) their union, intersection and concatenation are regular

Recall that for any two regular languages L_(1),L_(2) their union, intersection and
concatenation are regular as well.
Give an example of two non-regular languages L_(1),L_(2) such that their
concatenation is non-regular; Give an example of a non-regular lan-
guages L_(1) and a regular language L_(2) such that L_(1)\cup L_(2) is non-regular.
Bonus problem: Give an example of two non-regular languages
L_(1),L_(2) such that their concatenation is regular.
Hint: the choice of an alphabet is up to you, choose the simplest.
Recall that for any two regular languages L _ ( 1

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Programming Questions!

Q:

3 Problem Set 3 Recall that for any two regular languages Li. L. their union, intersection and concatenation are regular as well. 1. Give an example of two non-regular languages L1, L2 such that...

Q:

L _ ( 2 ) . Prove that L _ ( eq ) = L _ ( eq ) @L _ ( eq ) . Is it true that L _ ( eq ) = L _ ( eq ) ^ ( * ) ? Recall that for any two regular languages L _ ( 1 ) , L _ ( 2 ) their union,...

Q:

please solve 4 3, (10points) Recall, for a language L its complement is the set of strings over not in L, denoted - as L = {w LIC *. Let A be the language above and Let C = {w e {0, 1}* : w has even...

Q:

In this question assume that p and q are atomic formulae. (a) Compare and contrast path formulae and state formulae in temporal logic. [4 marks] (b) Describe and contrast the meanings of F(G p) and...

Q:

Please solove 3 3, (10points) Recall, for a language L its complement is the set of strings over not in L, denoted - as L = {w LIC *. Let A be the language above and Let C = {w e {0, 1}* : w has even...

Q:

1. [25 points] Let M be the DFA having the state diagram 1 40 91 42 1 Answer the following questions, giving a brief explanation of your answer. (One short sentence, or perhaps even a sentence...

Q:

** 2.3b Show expressiveness of finite automata* Prove by construction of a DFA or NFA that for all regular languages L, L1, L2, 1. Reg(L) (3A = NFA) L = L(A) their union is regular 2. 3. their...

Q:

. (20 pts) Give an example of each of the following. In all questions, the alphabet is {a,b}. If no example exists, answer "impossible". No justification needed. (a) A suffix of abbb of length 0.-El...

Q:

Show that the following languages are regular. Show that a language is regular by directly designing a DFA, NFA, or a regular expression for it. For some languages, it may be easier to first show...

Q:

Show that the following languages are regular. Show that a language is regular by directly designing a DFA, NFA, or a regular expression for it. For some languages, it may be easier to first show...

Q:

A friend of yours (Mike) has wealthy parents (Steve and Elaine) who are jointly worth $16,000,000. Mike notes neither of his parents are in the best of health and Steve (Dad) has been diagnosed as...

Q:

Give the principal organic product(s) expected when N-methylaniline reacts with each of the following reagents. (a) Br2 (b) Benzoyl chloride (c) Benzyl chloride (excess), then dilute -OH (d)...

Q:

Question 2 of 7 1 . 2 5 / 5 View Policies Show Attempt History Current Attempt in Progress Assume that on December 3 1 , 2 0 2 4 , Kimberly - Clark Corp. signs a 1 0 - year, non - cancelable lease...

Q:

Agricultural produce is Select one: a. Valued at each reporting period at fair value less cost of disposal b. The harvested product from biological asset c. All of the choices are correct regarding...