3 votes 3 votes The given set is 1,2,4,8, . . . . . 2^n in unary number system which is shown in BOLD below L = {1,11,1111,11111111, . . . . . . . . } Is it regular or CFL? Theory of Computation theory-of-computation regular-expression finite-automata identify-class-language + – iarnav asked Aug 11, 2017 iarnav 575 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes Language is neither regular and nor Cfl. Sandeep shahu answered Aug 12, 2017 Sandeep shahu comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Clearly, it is not a regular language. There is no DFA which can represent this language. Vivek Jain answered Aug 11, 2017 Vivek Jain comment Share Follow See 1 comment See all 1 1 comment reply iarnav commented Aug 11, 2017 reply Follow Share Then what L is this? Kindly tell. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Its neither regular nor cfl, notice number of 1's are growing in exponential manner, which we can't simulate using either dfa or pda. stblue answered Aug 11, 2017 stblue comment Share Follow See all 3 Comments See all 3 3 Comments reply iarnav commented Aug 11, 2017 reply Follow Share If we give the regular expression as 1+ then will it make that regular? 0 votes 0 votes stblue commented Aug 11, 2017 reply Follow Share Yes L = {$1^{+}$} is regular, you can easily draw DFA. But language in your question is not ${1^{+}}$. This language is L = {$1^{i}$ | i = $2^{n}$, n>=0} over $\sum$ = {1}. 0 votes 0 votes iarnav commented Aug 11, 2017 reply Follow Share Yes, you're right. My BAD it's not 1+ 0 votes 0 votes Please log in or register to add a comment.