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 Σ = {0, 1}. Give a regular expression that expresses the language {w | w...
Let Σ = {0, 1}. Give a regular expression that expresses the language {w | w contains exactly two 0s}.
Show that language B = {〈A〉| A is a DFA and L(A) = Σ* } is...
Show that language B = {〈A〉| A is a DFA and L(A) = Σ* } is decidable.
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
Prove by induction on n that if L is a language and R is a regular...
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 ....
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.
Prove that if a language L is regular, the suffix language of L is also regular.
Prove that if a language L is regular, the suffix language of L is also regular.
Let s and p be two particular strings over an alphabet Σ. Prove that the following...
Let s and p be two particular strings over an alphabet Σ. Prove that the following language M = {w ∈ Σ ∗ | w contains u as a substring but does not contain v as a substring} is regular. plz provide DFA and also simplified the DFA thx !
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT