Question

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.

Answer #1

L is a^n where n is multiple of 3 but not multiple of 5. So n can be 3,6,9,12 but not 15 . Then 18,21,24,27 but not 30 and so on.

So one thing you can observe is that n is multiple of 3 and not multiple of 15 . It means all those numbers which are divisible by 3 but not by 5 are multiples of 15 . So we can draw a DFA for this as below

This DFA accepts strings in which n is 3 ,6,9,12 then it dont accept 15 as you can see 15 is not final state. Then again it accepts 18,21,24,27 then not accept 30 and so on.

So since there exist a DFA for language L it means language L is a regular language.

Let L ⊆ Σ* be a regular language. Suppose a ∈ Σ and
define L\a = {x : ax ∈ L }. Show that L\a is regular.

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.

Let L1 be the language of the Regular Expression 1(1
+ 0)*.
Let L2 be the language of the Regular Expression 11*
0.
Let L3 be the language of the Regular Expression 1*
0.
Which of the following statements are true?
L2 L1
L2 L3
L1 L2
L3 L2

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).

Let swap_every_two be an operation on languages that is defined
as follows:
swap_every_two(L) = {a2a1a4a3 . . . a2na2n−1 | a1a2a3a4 . . .
a2n−1a2n ∈ L where a1, . . . , a2n ∈ Σ} In this definition, Σ is
the alphabet for the language L.
1. What languages result from applying swap every two to the
following languages:
(a) {1 n | n ≥ 0}, where the alphabet is {1}.
(b) {(01)n | n ≥ 0}, where the...

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.

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

Let Σ = {0,1}. Prove that the language { w | w contains the
substring 01001 } is regular by providing a finite automaton to
recognize the language. Include a state diagram, formal
description, and informal justification for the correctness of your
automaton.

The chopleft
operation of a regular language L is removing the leftmost symbol
of every string in L:
chopleft(L) = { w | vw
∈ L, with |v| = 1}.
Prove or disprove that
the family of regular languages is closed under the
chopleft operation.
Hint: If it’s regular,
give an idea of constructing an FA that accepts chopleft(L) using
an FA M that accepts L.
Otherwise, give a
counterexample.

8. (10 pts) Let M1 and M2 be two DFAs. Show that the following
language can also be accepted by a DFA: the set of all words w such
that w is accepted by M1 and w is not accepted by M2. (Hint:
Structural induction won’t help you.)

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 1 minute ago

asked 1 minute ago

asked 7 minutes ago

asked 12 minutes ago

asked 13 minutes ago

asked 23 minutes ago

asked 47 minutes ago

asked 51 minutes ago

asked 53 minutes ago

asked 1 hour ago

asked 1 hour ago

asked 1 hour ago