{"id":154119,"date":"2023-08-02T14:36:29","date_gmt":"2023-08-02T09:06:29","guid":{"rendered":"https:\/\/www.gkseries.com\/blog\/?p=154119"},"modified":"2023-08-02T14:36:41","modified_gmt":"2023-08-02T09:06:41","slug":"consider-the-following-sets-set-of-all-recursively-enumerable-languages-over-the-alphabet-01","status":"publish","type":"post","link":"https:\/\/www.gkseries.com\/blog\/consider-the-following-sets-set-of-all-recursively-enumerable-languages-over-the-alphabet-01\/","title":{"rendered":"Consider the following sets. Set of all recursively enumerable languages over the alphabet {0,1}"},"content":{"rendered":"\n

Q. Consider the following sets:<\/p>\n\n\n\n

S1.       Set of all recursively enumerable languages over the alphabet {0,1}<\/p>\n\n\n\n

S2.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Set of all syntactically valid C programs <\/p>\n\n\n\n

S3.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0Set of all languages over the alphabet {0,1}<\/p>\n\n\n\n

S4.       Set of all non-regular languages over the alphabet {0,1}<\/p>\n\n\n\n

Which of the above sets are uncountable?<\/p>\n\n\n\n

(A) S1 and S2<\/p>\n\n\n\n

(B) S3 and S4<\/p>\n\n\n\n

(C) S2 and S3<\/p>\n\n\n\n

(D) S1 and S4<\/p>\n\n\n\n

Ans: S3<\/sub>\u00a0and S4<\/sub><\/p>\n\n\n\n

Solution:<\/p>\n\n\n\n

    \n
  1. Recursively enumerable languages are countable.<\/li>\n\n\n\n
  2. Syntactically valid C program can be represented with CFG. CFG generates CFL, CFL is countable.<\/li>\n\n\n\n
  3. All languages over {0, 1} may not be countable, because they may also lie in the region of 2\u03a3*<\/sup>.<\/li>\n\n\n\n
  4. Set of regular languages are countable, non-regular languages may not be countable.<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"

    Q. Consider the following sets: S1.       Set of all recursively enumerable languages over the alphabet {0,1} S2.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 Set of all syntactically valid C programs S3.\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0Set of all languages over the alphabet {0,1} S4.       Set of all non-regular languages over the alphabet {0,1} Which of the above sets are uncountable? (A) S1 and S2 (B) S3 […]<\/p>\n","protected":false},"author":419,"featured_media":154120,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"footnotes":""},"categories":[5141],"tags":[5140],"class_list":["post-154119","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-gate","tag-gate-questions"],"_links":{"self":[{"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/posts\/154119","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/users\/419"}],"replies":[{"embeddable":true,"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/comments?post=154119"}],"version-history":[{"count":1,"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/posts\/154119\/revisions"}],"predecessor-version":[{"id":154121,"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/posts\/154119\/revisions\/154121"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/media\/154120"}],"wp:attachment":[{"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/media?parent=154119"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/categories?post=154119"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/tags?post=154119"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}