Question

Prove by induction on n that if L is a language and R is a regular expression such that L = L(R) then there exists a regular expression Rn such that L(Rn) = L n. Be sure to use the fact that if R1 and R2 are regular expressions then L(R1R2) = L(R1) · L(R2).

Answer #1

Solution:

**Base step:** When
we have
because this ensures
. Thus, when
, there is a regular expression
such that
.

**Induction hypothesis:** Suppose that for an
integer
there is a regular expression
such that
.

**Induction step:** Now consider
; we have

Since product of two regular expressions is a regular expression, letting , we conclude that there is a regular expression with .

**By induction we have now proved that for every
there is a regular expression
such that
.**

**Hope I answered the question.**

**If you have any doubts, or queries, feel free to
ask**

**I'll respond to you as soon as I can.**

**Have a nice day**

Given a language L, etc.
Show that the language L is a regular language.
To show that the language L is a regular language - find/design a
dfa that recognizes the language L.
Given a regular expression r, etc.
What is the language L, L = L(r)?
L(r) is the set of all strings etc.

5 A Non-Regular language
Prove that the language}L={www∣w∈{0,1}∗} is not regular.

a)
Let R be an equivalence relation defined on some set A. Prove
using induction that R^n is also an equivalence relation. Note: In
order to prove transitivity, you may use the fact that R is
transitive if and only if R^n⊆R for ever positive integer n
b)
Prove or disprove that a partial order cannot have a cycle.

Let Σ = {a}, and let L be the language
L={an :nisamultipleof3butnisNOTamultipleof5}.
Is L a regular language? HINT: Maybe instead of an explicit DFA
or regular expression, you can find another argument.

Prove that the language ?={?^??^??^?:?≤?+?}is not regular

Consider the language defined by L =
{aibmcn | i > 0, n > m >
0 }
Is L regular or not? Prove it

Prove using induction: There is no rational number r
for which r2=2.

Suppose A and B are regular language. Prove that AB is regular.

For Automata class:
Let L be a regular language over the binary alphabet. Consider
the following language over the same alphabet: L' = {w | |w| = |u|
for some u ∈ L}. Prove that L' is regular.

Are the following languages over {a, b} regular? If they are
then prove it. If they are not prove it with the Pumping Lemma
{an bm | m != n, n >= 0}
{w | w contains the substring ‘aaa’ once and only once }
Clear concise details please, if the language is regular,
provide a DFA/NFA along with the regular expression. Thank you.
Will +1

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 7 minutes ago

asked 10 minutes ago

asked 18 minutes ago

asked 20 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago

asked 2 hours ago

asked 2 hours ago

asked 2 hours ago