19 votes 19 votes What is the type of the language $L$, where $L=\{a^n b^n \mid 0 < n < 327 \text{-th prime number} \}$ Theory of Computation gate1988 normal descriptive theory-of-computation identify-class-language + – go_editor asked Dec 18, 2016 recategorized Apr 16, 2021 by Lakshman Bhaiya go_editor 2.9k views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply Rishav Kumar Singh commented Oct 27, 2018 reply Follow Share Here n is finite and finite language must be regular Languages. # If n >0 and n not mentioned prime only then it would be DCFL. # if n>0 and prime then it would be CSL 5 votes 5 votes Shiva Sagar Rao commented Jan 30, 2021 reply Follow Share Why does this question contain algorithms tag? 0 votes 0 votes Please log in or register to add a comment.
Best answer 27 votes 27 votes Here $n$ is finite and finite language must be regular. If $n$ is not restricted, then it would be DCFL. kirti singh answered Dec 18, 2016 edited Jun 15, 2018 by Milicevic3306 kirti singh comment Share Follow See all 14 Comments See all 14 14 Comments reply 1gate_cracker commented Nov 11, 2017 reply Follow Share but here limit is prime no.and we know that prime no. not belongs to regular lang. pls clear my doubt if i'm wrong 0 votes 0 votes Puja Mishra commented Nov 19, 2017 reply Follow Share Does nt matter with limit ... N is finite ... so regular .. 3 votes 3 votes Digvijay Pandey commented Feb 21, 2018 reply Follow Share "If n is not restricted, then it would be DCFL" Shouldn't be CSL? 1 votes 1 votes joshi_nitish commented Feb 21, 2018 reply Follow Share sir, given language is $a^nb^n$, with no restriction on $n$, it would be DCFL 0 votes 0 votes Digvijay Pandey commented Feb 21, 2018 reply Follow Share So no restriction means 327 is not given, right? Still, it should be prime, No? 1 votes 1 votes joshi_nitish commented Feb 21, 2018 reply Follow Share sir, i am taking no restriction as 'n' could be anything(no restriction on even being prime or non prime). 0 votes 0 votes jatin khachane 1 commented Oct 14, 2018 reply Follow Share @Digvijay Pandey sir $a^{n}b^{n} | n = prime\: number$ $a^{n}b^{n} | n = even\: number$ Are this languages CFL/NCFL ?? 0 votes 0 votes mrinmoyh commented Sep 17, 2019 reply Follow Share $L = {a^{1}b^{1}, a^{3}b^{3},a^{5}b^{5},a^{7}b^{7},...........}$ here though language is finie but how can we make FA so that all thses strings of L will be accepted?? please reply anyone. 0 votes 0 votes oldDoctor commented Sep 17, 2019 reply Follow Share Since it is finite but there is no particular pattern involved, the no of states required in a FA might be the summation of twice #a's and #b's across all the prime nos till the 327th prime no. 0 votes 0 votes Satbir commented Sep 17, 2019 reply Follow Share We will make a NFA which which will have various non-deterministic paths. Like in one path it generates $ab$ in another path it generates $aabb$....in 326th path it generates $a^{326}b^{326}$ after making this convert the NFA to DFA 0 votes 0 votes mrinmoyh commented Sep 17, 2019 reply Follow Share Basically creating separate DFA for all strings in that set & then eventually Union them. 0 votes 0 votes Satbir commented Sep 17, 2019 reply Follow Share Yes...it is also correct. 0 votes 0 votes iwasifirshad commented Jul 4, 2020 i edited by JAINchiNMay Nov 20, 2022 reply Follow Share But sir here, 'n' is a power of both 'a' and 'b' and we know that Regular Language uses Finite Automata, but FA doesn't have memory to store n.HOW CAN IT BE 'REGULAR LANGUAGE'? 0 votes 0 votes Gupta731 commented Aug 31, 2020 reply Follow Share @iwasifirshad But as you see $n$ is restricted to $0<n<327$th prime number, which makes the language finite. Hence Regular. 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes Regular language rishu_darkshadow answered Oct 5, 2017 rishu_darkshadow comment Share Follow See all 4 Comments See all 4 4 Comments reply Puja Mishra commented Nov 19, 2017 reply Follow Share Explain .... 0 votes 0 votes rishu_darkshadow commented Nov 23, 2017 reply Follow Share Because it is finite and every finite language is regular.... 1 votes 1 votes Puja Mishra commented Jan 15, 2018 reply Follow Share Finite and u can think it as union of regular language .... Specific ... 1 votes 1 votes raja11sep commented Jul 19, 2021 reply Follow Share Finite union 0 votes 0 votes Please log in or register to add a comment.