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 Show 7 previous comments 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.