{"id":219633,"date":"2025-05-26T12:44:35","date_gmt":"2025-05-26T12:44:35","guid":{"rendered":"https:\/\/learnexams.com\/blog\/?p=219633"},"modified":"2025-05-26T12:44:37","modified_gmt":"2025-05-26T12:44:37","slug":"perform-the-pairwise-disjointness-test-for-the-following-grammar-rules","status":"publish","type":"post","link":"https:\/\/www.learnexams.com\/blog\/2025\/05\/26\/perform-the-pairwise-disjointness-test-for-the-following-grammar-rules\/","title":{"rendered":"Perform the pairwise disjointness test for the following grammar rules."},"content":{"rendered":"\n<p>Perform the pairwise disjointness test for the following grammar rules.<\/p>\n\n\n\n<p>1. S ? aSb | bAA<\/p>\n\n\n\n<p>2. A ? B{aB} | a<\/p>\n\n\n\n<p>3. B ? aB | a<\/p>\n\n\n\n<p><strong><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-ast-global-color-1-color\">The Correct Answer and Explanation is:<\/mark><\/strong><\/p>\n\n\n\n<p>To perform the <strong>pairwise disjointness test<\/strong> on grammar rules, we check whether <strong>each alternative in a rule has disjoint (non-overlapping) FIRST sets<\/strong>. This ensures that a predictive parser (like an LL(1) parser) can decide which production to use by looking at only the next input symbol.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>1. Rule: S \u2192 aSb | bAA<\/strong><\/h3>\n\n\n\n<p><strong>Alternatives:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>aSb<\/li>\n\n\n\n<li>bAA<\/li>\n<\/ul>\n\n\n\n<p><strong>FIRST(aSb) = {a}<\/strong><br><strong>FIRST(bAA) = {b}<\/strong><\/p>\n\n\n\n<p>\u2705 <strong>Disjoint<\/strong>: {a} \u2229 {b} = \u2205 \u2192 <strong>PASS<\/strong><\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>2. Rule: A \u2192 B aB | a<\/strong><\/h3>\n\n\n\n<p>Let\u2019s analyze each part.<\/p>\n\n\n\n<p>First, we need FIRST(B) to compute FIRST(B aB).<\/p>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>3. Rule: B \u2192 aB | a<\/strong><\/h3>\n\n\n\n<p>All productions of B start with <strong>&#8216;a&#8217;<\/strong>, so:<\/p>\n\n\n\n<p><strong>FIRST(B) = {a}<\/strong><\/p>\n\n\n\n<p>Now go back to <strong>Rule 2<\/strong>:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>FIRST(B aB) = FIRST(B) = {a}<\/li>\n\n\n\n<li>SECOND alternative is just &#8216;a&#8217; \u2192 FIRST(a) = {a}<\/li>\n<\/ul>\n\n\n\n<p>So, FIRST(B aB) = {a}<br>FIRST(a) = {a}<\/p>\n\n\n\n<p>\u274c <strong>Not disjoint<\/strong>: {a} \u2229 {a} \u2260 \u2205 \u2192 <strong>FAIL<\/strong><\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>3. Rule: B \u2192 aB | a<\/strong><\/h3>\n\n\n\n<p>Alternatives:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>aB<\/li>\n\n\n\n<li>a<\/li>\n<\/ul>\n\n\n\n<p><strong>FIRST(aB) = {a}<\/strong><br><strong>FIRST(a) = {a}<\/strong><\/p>\n\n\n\n<p>\u274c Not disjoint: {a} \u2229 {a} \u2260 \u2205 \u2192 <strong>FAIL<\/strong><\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">\u2705 Summary of Pairwise Dis<\/h2>\n\n\n\n<p>The <strong>pairwise disjointness test<\/strong> is a method used to check if a grammar is suitable for <strong>predictive parsing<\/strong> (typically LL(1)). A grammar passes this test if, for each non-terminal with multiple production alternatives, the parser can unambiguously choose the correct production based solely on the next input symbol. This requires the <strong>FIRST sets<\/strong> of each alternative to be <strong>disjoint<\/strong> (non-overlapping).<\/p>\n\n\n\n<p>For Rule 1: <code>S \u2192 aSb | bAA<\/code>, the FIRST sets are {a} and {b}, respectively. Since there\u2019s no overlap, the parser can distinguish which production to choose when it sees either &#8216;a&#8217; or &#8216;b&#8217;. Hence, Rule 1 <strong>passes<\/strong> the disjointness test.<\/p>\n\n\n\n<p>In Rule 2: <code>A \u2192 B aB | a<\/code>, we first evaluate Rule 3 (<code>B \u2192 aB | a<\/code>) to get FIRST(B). Both alternatives of B begin with &#8216;a&#8217;, so FIRST(B) = {a}. Therefore, both <code>B aB<\/code> and <code>a<\/code> in Rule 2 start with &#8216;a&#8217;, resulting in overlapping FIRST sets. This ambiguity makes it impossible for a parser to choose the correct production without further lookahead, so <strong>Rule 2 fails<\/strong> the test.<\/p>\n\n\n\n<p>Rule 3 (<code>B \u2192 aB | a<\/code>) also has both alternatives starting with &#8216;a&#8217;, resulting in identical FIRST sets. Hence, it also <strong>fails<\/strong> the pairwise disjointness test.<\/p>\n\n\n\n<p>This test is critical in compiler design, especially for constructing efficient LL(1) parsers that require unambiguous decisions based on a single input token.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img decoding=\"async\" src=\"https:\/\/learnexams.com\/blog\/wp-content\/uploads\/2025\/05\/learnexams-banner6-43.jpeg\" alt=\"\" class=\"wp-image-219634\"\/><\/figure>\n","protected":false},"excerpt":{"rendered":"<p>Perform the pairwise disjointness test for the following grammar rules. 1. S ? aSb | bAA 2. A ? B{aB} | a 3. B ? aB | a The Correct Answer and Explanation is: To perform the pairwise disjointness test on grammar rules, we check whether each alternative in a rule has disjoint (non-overlapping) FIRST [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","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-5)","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-5)","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-5)","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":[25],"tags":[],"class_list":["post-219633","post","type-post","status-publish","format-standard","hentry","category-exams-certification"],"_links":{"self":[{"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/posts\/219633","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/comments?post=219633"}],"version-history":[{"count":0,"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/posts\/219633\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/media?parent=219633"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/categories?post=219633"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.learnexams.com\/blog\/wp-json\/wp\/v2\/tags?post=219633"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}