How to prove language L is not regular? L = {a^3^k | k element N} is subset of {a,b}*
L = {a^3^k | k element N} is subset of {a,b}*
I have to prove that the language L is not regular, but I don't know what the subset means for the proof.
{a^3^k | k element N} should be regular because I can draw a DFA and I also can draw a DFA of {a, b}.
It's not regular. In fact a very good rule of thumb to tell at a glance is if the language is trying to count characters in a non-repeatable fashion.
You can't count with a single regular expression a sequence like 1, 3, 9, 27 while making sure all the other counts fail, you need something repeatable like \d{5} in normal regex notation.
I'll leave the proof up to you since this is obviously homework, just clarifying the misconception that this is regular because you can draw the first two elements. Sure you can, but you can't draw the generic term in a general way!
- Math.Sin() gives incorrect value
- How to run my python script when the sunOS is start booting
- Express-session: not resetting cookie expiration on each request
- Getting a stack overflow exception when normalizing a vector
- Edit default summary function in R gives error for multiple variables
- What was a For loop? Why isn't it needed in R?
- How to use download button in shiny and save results in various formats (csv, texte, pdf, spss...)?
- Why are there two assignment operators, `<-` and `->` in R?
- lm()$assign: what is it?
- How to get the value of list(...) in R and S functions
- Design matrix for MLM from library(lme4) with fixed and random effects
- how to generate elements not included in my sample
- Create a matrix with gradually changing values without a for loop
- Emacs ESS and S-plus ( S+ ) 8.1 compatability
- How to lag date-index in a time-series in R?
- Nonlinear regression in R / S
- Calling R from S-Plus?