1

I would like to determine the lookahead set $\newcommand{\LA}[1]{\mathrm{LookAhead}_{#1}}\LA{1}(S)$ for the productions $P$ \begin{align*} \newcommand{\rewrite}{\longrightarrow} S &\rewrite Ab & S &\rewrite Cd & A &\rewrite aA \\ A &\rewrite \epsilon & C &\rewrite cC & C &\rewrite \epsilon\,. \end{align*} of the grammar $\newcommand{\set}[1]{\left\{#1\right\}}G = \newcommand{\perm}[1]{\left\langle#1\right\rangle}\perm{\Sigma, V, P, S} = \perm{\set{a, b, c, d}, \set{S, A,C}, P, S}$. Now in my head this is \begin{align*} \LA{1}(S) &= \LA{1}(A) \cup \LA{1}(C) \\ &= \set{a, \epsilon} \cup \set{c, \epsilon} = \set{\epsilon, a, c}, \end{align*} as the productions where $S$ is on the left side have $A$ and $C$ as the first variable, but once again my plans have been thwarted by an automatic assessment system. According to the submit form, the correct answer does not involve all of the strings $a$, $b$ and $\epsilon$. My guess is that the culprit is $\epsilon$, but I'm not sure why.

The set $\LA k (\alpha)$ is defined as \begin{align}\newcommand{\derive}{\Longrightarrow}\tag{1}\label{eq:LA} \LA k (\alpha) &= \set{ x \in \Sigma^\ast \mid \alpha\derive_G^\ast x, |x| < k } \\ &\cup \set{ x \in\Sigma^\ast \mid \alpha \derive_G^\ast x\beta, |x| = k, \beta \in (\Sigma\cup V)^\ast }, \end{align} but I don't see why this wouldn't allow empty strings $\epsilon$. What am I not getting here?

Edit

After the answer of @CalumGilhooley, I get the following derivations: \begin{alignat*}{3} S &\derive_G Ab &&\derive_G \epsilon b &&\derive_G b \\ S &\derive_G Ab &&\derive_G aAb &&\derive_G \ldots \\ S &\derive_G Cd &&\derive_G \epsilon d &&\derive_G d \\ S &\derive_G Cd &&\derive_G cCd &&\derive_G \ldots \end{alignat*} With one lookahead, we apply the productions until we end up with a single alphabet $\alpha\in\Sigma$ (a string of length one) at the front of the derivation, so if we run into the empty string, we need to go deeper. With a lookahead of length 2, based on the definition \eqref{eq:LA}, we would repeat the process until there were strings of length 2 and less in front of the derived strings, and so on.

With this logic the lookahead set $\LA 1(S) = \set{a, b, c, d}$. No empty strings attached.

sesodesa
  • 701

1 Answers1

1

I think your mistake is in the line $\operatorname{LookAhead}_1(S) = \operatorname{LookAhead}_1(A) \cup \operatorname{LookAhead}_1(C).$

This is false because the rules $A \longrightarrow \epsilon$ and $C \longrightarrow \epsilon$ allow $S$ to produce $b$ and $d,$ respectively.

I get $\operatorname{LookAhead}_1(S) = \{a, b, c, d\}.$ Is that correct?

Calum Gilhooley
  • 12,174
  • So the idea is that empty productions of the form $A \longrightarrow\epsilon$ can "eat away" at other productions, where they occur. This actually does make sense. I need to make sure I get the same result as you by applying this logic, before I press Submit again. I only have one more attemp left. – sesodesa Apr 09 '20 at 16:26
  • Indeed, don't rush! It's decades since I studied this stuff, so I could be up a gum tree. As I see it, the rule $A \longrightarrow\epsilon$ implies $Ab \Longrightarrow_G b,$ which together with the rule $S \longrightarrow Ab$ implies $S \Longrightarrow_G^* b,$ etc. – Calum Gilhooley Apr 09 '20 at 16:42
  • I wonder if $\epsilon$ should be allowed after all. In the definition of the set $\operatorname{LookAhead}_k(\alpha)$, the strings $x$ are in the Kleene closure of the alphabet $\Sigma$, meaning strings of zero length should also be allowed? In this case the answer would be $\operatorname{LookAhead}_1(S) = {a,b,c,d,\epsilon}$ – sesodesa Apr 09 '20 at 17:00
  • Any derivation from $S,$ apart of course from the unique trivial derivation $S \Longrightarrow_G^* S,$ of length zero, must start with one step, and the first step must produce a string ending in either $b$ or $d.$ Because all the production rules are context-free, any string (with or without nonterminal symbols) derived from $S$ apart from $S$ itself must end in $b$ or $d.$ Therefore the empty string cannot be derived from $S.$ (This seems clear, but my recollection of the concepts and terminology of formal language theory remains hazy, so you'd better keep checking that I'm making sense!) – Calum Gilhooley Apr 09 '20 at 17:34
  • Right, I'm just really trying to hammer this into my head. Looking at the definition of $\operatorname{LookAhead}_k(\alpha)$, it does say that whatever the string $x$ is, it has to be derivable from $\alpha$. That's the key. That's what the notation $S \Longrightarrow _G^\ast x$ means. – sesodesa Apr 09 '20 at 18:08
  • Well, no, the $x$ in the second subset of $\operatorname{LookAhead}_k(\alpha)$ in (1) need not be derivable from $\alpha,$ but that $x$ cannot be empty. – Calum Gilhooley Apr 09 '20 at 18:13