Q. Consider the following problems. \ud835\udc3f(\ud835\udc3a) denotes the language generated by a grammar \ud835\udc3a. \ud835\udc3f(\ud835\udc40) denotes the language accepted by a machine \ud835\udc40.<\/p>\n\n\n\n
I. For an unrestricted grammar \ud835\udc3a and a string \ud835\udc64, whether \ud835\udc64 \u2208 \ud835\udc3f(\ud835\udc3a)<\/p>\n\n\n\n
II. Given a Turing machine <\/span>M<\/em>, whether <\/span>L<\/em>(<\/span>M<\/em>) is regular<\/span><\/p>\n\n\n\n III. Given two grammars \ud835\udc3a<\/span>1<\/sub> and \ud835\udc3a<\/span>2<\/sub>, whether \ud835\udc3f(\ud835\udc3a<\/span>1<\/sub>) = \ud835\udc3f(\ud835\udc3a<\/span>2<\/sub>)<\/span><\/p>\n\n\n\n IV. Given an NFA N<\/em>, whether there is a deterministic PDA P <\/em>such that N <\/em>and P<\/em> accept the same language.<\/em><\/p>\n\n\n\n Which one of the following statements is correct?<\/p>\n\n\n\n (A) Only I and II are undecidable (B) Only III is undecidable<\/p>\n\n\n\n (C) Only II and IV are undecidable\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0\u00a0 (D) Only I, II and III are undecidable<\/p>\n\n\n\n Ans: Only I, II and III are undecidable<\/p>\n\n\n\n <\/p>\n","protected":false},"excerpt":{"rendered":" Q. Consider the following problems. \ud835\udc3f(\ud835\udc3a) denotes the language generated by a grammar \ud835\udc3a. \ud835\udc3f(\ud835\udc40) denotes the language accepted by a machine \ud835\udc40. I. For an unrestricted grammar \ud835\udc3a and a string \ud835\udc64, whether \ud835\udc64 \u2208 \ud835\udc3f(\ud835\udc3a) II. Given a Turing machine M, whether L(M) is regular III. Given two grammars \ud835\udc3a1 and \ud835\udc3a2, whether […]<\/p>\n","protected":false},"author":419,"featured_media":160316,"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-160315","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\/160315","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=160315"}],"version-history":[{"count":1,"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/posts\/160315\/revisions"}],"predecessor-version":[{"id":160317,"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/posts\/160315\/revisions\/160317"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/media\/160316"}],"wp:attachment":[{"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/media?parent=160315"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/categories?post=160315"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.gkseries.com\/blog\/wp-json\/wp\/v2\/tags?post=160315"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}