Question

Let Σ = {a}, and let L be the language L={an :nisamultipleof3butnisNOTamultipleof5}. Is L a regular...

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.

Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

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.

0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Let L ⊆ Σ* be a regular language. Suppose a ∈ Σ and define L\a =...
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...
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...
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
Let swap_every_two be an operation on languages that is defined as follows: swap_every_two(L) = {a2a1a4a3 ....
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...
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.
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...
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...
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...
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.)
Are the following languages over {a, b} regular? If they are then prove it. If they...
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
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT