Question

6. ProveL={yy|y∈Σ∗}is not regular.

6. ProveL={yy|y∈Σ∗}is not regular.

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

Homework Answers

Answer #1

For a language to being a regular language, we know that if we can build a Finite state automata for any language then it is regular.

FSA has a property to remember pattern, but it does not have any memory to store some thing.

For language , we can easily remember pattern of y but FSM doesn't have memory to store y and compare to some string y' to match y=y'.

Therefore we can't build any FSM for the language L. Hence it is not regular language.

Note : However it can be build using push down automate. But this is beyond this question.

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.
Solve the differential equation yy''= (1/2)(y')2 by using the substitution u=y'
Solve the differential equation yy''= (1/2)(y')2 by using the substitution u=y'
Find the general solution of the ODE: x2(y′)2 + yy′(2x+y) + y2= 0
Find the general solution of the ODE: x2(y′)2 + yy′(2x+y) + y2= 0
solve by separation variable 3, xydx-(1+x^2) dy=0 4, xy'+y=y^2 5,yy'=xe^2+y^2 6, xsiny.y'=cosy 7, y'=x^2 y/1+x^3 xsiny.y'+cosy
solve by separation variable 3, xydx-(1+x^2) dy=0 4, xy'+y=y^2 5,yy'=xe^2+y^2 6, xsiny.y'=cosy 7, y'=x^2 y/1+x^3 xsiny.y'+cosy
If a field population started with 50% standard (YY) plants and 50% (yy) plants, how wound...
If a field population started with 50% standard (YY) plants and 50% (yy) plants, how wound you expect frequencies of the two alleles (Y and y) to change in future generations?
A dyhybrid cross was performed with the following parental generation Yy,Aa   X   Yy,Aa   . What is...
A dyhybrid cross was performed with the following parental generation Yy,Aa   X   Yy,Aa   . What is the expected ratio of the phenotypes in F1?   Show Work!!!     (Y=green leaf, y=yellow leaf: A= purple stem, a= green stems
Solve the initial value problem, if possible. yy'(t) = t8, y(0) = 9
Solve the initial value problem, if possible. yy'(t) = t8, y(0) = 9
Find yy as a function of xx if y(4)−12y‴+36y″=0, y(0)=5,  y′(0)=14,  y″(0)=36,  y‴(0)=0 y(x)=?
Find yy as a function of xx if y(4)−12y‴+36y″=0, y(0)=5,  y′(0)=14,  y″(0)=36,  y‴(0)=0 y(x)=?
solve by separation variable 5, yy'=xe^2+y^2 7, y'=x^2 y/1+x^3 xsiny.y'+cosy
solve by separation variable 5, yy'=xe^2+y^2 7, y'=x^2 y/1+x^3 xsiny.y'+cosy
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.
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT