Question

Question 9. Consider the language {a"b" : n >0}. (i) Is this a regular language? Why or why not? (ii) Is this a recursively enumerable language? Why or why not? Question 10. Consider the function defined by f(n) = 2 where n is a positive integer. (i) Can this function be computed by a Turing machine? Why or why not? (ii) Is this function primitive recursive? Why or why not?

Answer 1

9)
given L = {a^nb^n :0<=n}
i)
Given language is not regular
proof using pumping lemma:
let take a string w belongs to L
w = aabb
now divide w into xyz, such that 0<|y|
a|a|bb
x|y|z
x=a,y=a,z=bb
now by pumping lemma, for all 0<i, xy^iz belongs to L
let i=1, xy^1z = aabb belongs to L
i=2, xy^2z = xyyz = aaabb doesn't belongs to L
since, xy^2z doesn't belongs to L which violates pumping lemma, hence L is not regular

ii)
yes it is recursively enumerable
given language is context free,
every context free language is recursive
and every recursive language is recursively enumerable
hence given language is recursively enumerable

for all 970 the pumping limma for regiar lamgelegesi- Let l be a regular lemgriege Then, there exists a constant ac whose value depends upon 2) such that for every string belonging to the languege L end lwan, broken into 3 parts x,y,z. nyt, 476; and (xylsn, The string eyiz alsoned belongs to hi W can be such that CS CamScanner

Note: As per HOMEWORKLIB POLICY, I am allowed to answer only 1 question(including sub-parts)
on a single post, kingly post the remaining questions seperately and i will try to answer them
Sorry for the inconvenience caused, thank you