Question 3. Write down a regular expression that denotes the following language.
L = {a mb n : m + n is even}
Question 4. Let L1 be the language denoted by ab∗ a ∗ and let L2 be the language denoted by a ∗ b ∗ a
Write a regular expression that denotes the language L1 ∩ L2.
Solution:
Question 3)
The above problem gives rise to two possible cases.
m+n must be even. To achieve this, we must see that both m and n must be even or both must be odd. Only then m+n can be even.
The two cases are as follows:
n is even and m is even:
The regular expression for this is as follows.
(aa)*(bb)*
m is odd and n is odd:
a(aa)*b(bb)*
Combining the above two cases, the regular expression is as follows.
(aa)*(bb)* + a(aa)*b(bb)*.
Note:
Please see that as per the guidelines only one question can be answered when multiple questions are posted under single question.
In case of multiple choices, upto 4 questions can be answered.
Thank you.
Question 3. Write down a regular expression that denotes the following language. L = {a mb...
Question 3. Write down a regular expression that denotes the following language. L = {a^m b^n : m + n is even}
Question 4. Let L1 be the language denoted by ab∗ a ∗ and let L2 be the language denoted by a ∗ b ∗ a Write a regular expression that denotes the language L1 ∩ L2.
Let L 1be the language denoted by ab ∗ a ∗ and let L 2 be the language denoted by a ∗ b ∗ a Write a regular expression that denotes the language L 1 ∩ L 2 .
Write a legal regular expression for the following regular language. L = { w | w ∊ (0 + 1)* and w contains an even number of 1’s AND an even number of 0’s}.
Question 1: Every language is regular T/F Question 2: There exists a DFA that has only one final state T/F Question 3: Let M be a DFA, and define flip(M) as the DFA which is identical to M except you flip that final state. Then for every M, the language L(M)^c (complement) = L( flip (M)). T/F Question 4: Let G be a right linear grammar, and reverse(G)=reverse of G, i.e. if G has a rule A -> w B...
HW03 - 1 to 4 Problem 1 Find a regular expression for the set ^a"bm: (n + m) is odd Problem 2 Give regular expressions for the following languages. 3. The complement of L 4. The complement of L2 Problem 3 Find a regular expression for L = {w: na(w) and nb(w) are both even } Problem 4 Find dfa's that accept the following languages A. L-L(ab a)UL((ab) ba)
Question 7 10 pts Let = {a,b,c}. Write a left-linear grammar for the language denoted by the regular expression p=(cab)* (ab + bc + acb) (abc)*a*
(4) [20 pts] Let L be the language defined by a regular expression (O | 1)0+(01 1)). over t alphabet f(o,1, +) (a) (4pt) Write down 5 different words from L (b) (8pt) Describe L using words. (c) (8pt) Draw an automaton accepting L (ideally, deterministic). (4) [20 pts] Let L be the language defined by a regular expression (O | 1)0+(01 1)). over t alphabet f(o,1, +) (a) (4pt) Write down 5 different words from L (b) (8pt) Describe...
1. Construct a DFSM to accept the language: L w E ab): w contains at least 3 as and no more than 3 bs) 2. Let E (acgt and let L be the language of strings consisting of repeated copies of the pairs at, ta, cg. ge. Construct both a DFSM to accept the language and a regular expression that represents the language. 3. Let ab. For a string w E , let w denote the string w with the...
4. A regular expression for the language over the alphabet fa, b) with each string having an even number of a's is (b*ab*ab*)*b*. Use this result to find regular expressions for the following languages a language over the same alphabet but with each string having odd number of a's. (3 points) a. b. a language over the same alphabet but with each string having 4n (n >- 0) a's. (3 points)