2 votes 2 votes L1={wlwR∣w∈{a,b}∗,l∈{a,b} } which type of language is this DCFL or NDCFL? (note that l∈{a,b} not {a,b}*) I feel its NDCFL can you also tell how PDA will look like? Denson George asked Jan 10, 2017 Denson George 1.6k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes Yeah this is not only DCFL but also regular. So, FSA is enough. It has to accept the regex of the form a(a+b)*a+b(a+b)*b + a + b Nithish answered Jan 10, 2017 • edited Jan 12, 2017 by Sushant Gokhale Nithish comment Share Follow See all 3 Comments See all 3 3 Comments reply Sushant Gokhale commented Jan 12, 2017 reply Follow Share Its PDA 0 votes 0 votes Nithish commented Jan 12, 2017 reply Follow Share How? A regex can be accepted by a FSA right? 0 votes 0 votes Sushant Gokhale commented Jan 12, 2017 reply Follow Share See below. Sourabh has given explanation. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes no it will be ncfl ryt? . because for w supppose it will be aaab than l can be any (a+b) so here we can't do the work determiniatically so it will be cfl but not dcfl focus _GATE answered Jan 10, 2017 focus _GATE comment Share Follow See all 10 Comments See all 10 10 Comments reply Denson Denz George commented Jan 10, 2017 reply Follow Share Yes that is what I was thinking.. any idea on the PDA? 0 votes 0 votes Sushant Gokhale commented Jan 12, 2017 reply Follow Share .... 0 votes 0 votes Sushant Gokhale commented Jan 12, 2017 reply Follow Share I think it should be regular. a + b + a { [ (a+b) (a+b) ]* (a+b) } a + b { [ (a+b) (a+b) ]* (a+b) } b 0 votes 0 votes saurabh rai commented Jan 12, 2017 reply Follow Share check on abaaa 0 votes 0 votes Sushant Gokhale commented Jan 12, 2017 reply Follow Share oohhhh....Thanks Sourabh.Got it. 0 votes 0 votes Nithish commented Jan 12, 2017 i reshown by Nithish Jan 12, 2017 reply Follow Share We can construct a NFA such that it accepts string with starting and ending with same letter. Which would look like this, This NFA can be converted to DFA with conventional methods. 0 votes 0 votes Sushant Gokhale commented Jan 12, 2017 reply Follow Share we cant have (a+b)* in between because L$\in${a, b} and not L$\in${a, b}* 0 votes 0 votes Nithish commented Jan 12, 2017 reply Follow Share @Sushant , I have edited my comment, this NFA doesnot accept ab, but accepts strings with same starting and ending letters and accepts (a+b). Can you check it? 0 votes 0 votes Sushant Gokhale commented Jan 12, 2017 reply Follow Share @Nithish. abaaa is accepted by your NFA but not by def. of language. I made the same mistake. Observe closely. 0 votes 0 votes Nithish commented Jan 12, 2017 reply Follow Share @Sushant, Got it. My bad. Wasted lot of time. This can be accepted by NPDA only. 1 votes 1 votes Please log in or register to add a comment.