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
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.
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.
Consider the NFA N with states labeled q1, q2 and q3, where q1 is the start...
Consider the NFA N with states labeled q1, q2 and q3, where q1 is the start state and q2 and q3 are the final (accepting) states. The transition function for N is δ(q1,a) = {q1}, δ(q1,b) = {q1,q2},  δ(q2,a) = {q3}, δ(q2,b)= ∅, δ(q3,a)= ∅, and δ(q3,b)= ∅. Let L be the language recognized by N i.e. L(N). a) Draw the state diagram for N. b) Describe in plain English what's in the language L. c) Via the construction NFA to...
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.
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT