New answers tagged

2

Your language $L$ is not regular. Suppose that it was regular, then its complement $\overline{L}$ is also regular and the intersection $M = \{ a^j,b^k \mid j=k \vee j \not\equiv k \pmod{3} \}$ between $\overline{L}$ and $\{a^j,b^k \mid j,k \ge 0\}$ is regular. Let $n$ a sufficiently large multiple of $3$ and consider the word $a^n b^n$. By the pumping ...


2

Your informal description of your language could certainly be made more precise, in the same way as you could make the description of any (mathematical) set more precise until you've written the description out in mathematical notation. In that sense, EBNF is similar to what you get when you recast an informal description of a language into a mathematical ...


3

This follows from the pumping lemma, if you examine the proof closely enough.


0

Your original grammar is not only left-recursive, it is also ambiguous. Left-recursion only matters to certain parsing techniques, but ambiguous grammars are, by definition, impossible to parse with a deterministic parser. And removing left-recursion does not in general fix ambiguity. The ambiguity is in the production R → R + R which allows 1 + 2 + 3 to ...


0

Your factoring is wrong. It should be (written as regular espressions): $\begin{align*} R &\to (L \mid \operatorname{num}) (+ R)^* \end{align*}$ Thus the grammar with left recursion fixed is: $\begin{align*} S &\to L = R \\ L &\to * L \mid \operatorname{id} \\ R &\to L R' \mid \operatorname{num} R' \\ R' &\to + R ...


1

Sure, the idea is basically that you're going to turn the first 0 into blank, and then go search for the last 1 and turn it in into blank, then go back to the beginning and proceed recursively in the same fashion. Here's an implementation on the online turing machine simulator


1

Yes, listing out all the transitions would be tedious so I'll just give you the high level algorithm (the idea is to iteratively match the first 0 with the last 1, while deleting both of them). Starting from the first symbol on the tape do the following: If the current symbol is $\varepsilon$: accept If the current symbol is $1$: reject Delete the current ...


3

I'll just show how to build a grammar for $L_1 = \{ u\#v, |u|_a > |v|_a \}$. Then it'll be straightforward to combine 4 similar grammars into a grammar for $L$. The idea is to write $u\#v$ as $xay\#v$ with $x,y,v \in \{a,b\}^*$ and $|y|_a = |v|_a$. The construction of $y\#v$ is handled by the non-terminal $Z$ which "grows" it from the center. $$ \...


0

This is not a CFL. We can prove this using pumping lemma for CFL. We prove it as follows: Consider the string $s = 0^n1^n0^n\#0^n1^n0^n \in L$. By pumping lemma, for a significantly large $n$, we can split the string in five parts: $u,v,w,x,y$ such that $s = uvwxy$, $|vx| > 0$, and $uv^mwx^my \in L$ for all $m$. Basically, you have to find out two ...


1

Consider the word $w = 0^n1^n0^n \# 0^n1^n0^n \in L$ for a sufficiently large value of $n$. By the pumping lemma for context-free languages, we know that if $L$ is context-free then there are$a,b,c,d,e = \Sigma^*$, with $|bcd| < n$ and $|bd|>1$ such that $w=abcde$ and, for every $i \ge 0$, $a b^i c d^i e\in L$. Notice that neither $b$ nor $d$ can ...


2

Let us replace $a$ with $\nearrow$ and $b$ with $\searrow$. Given a sequence of arrows, we construct a "walk" in which each arrow's tail starts from the preceding arrow's head. We keep track of the height. You are interested in walks which end up at or above the starting height. Given such a walk $w = w_1 \ldots w_n$, let $i \in \{0,\ldots,n\}$ be the last ...


2

Here is an unambiguous grammar for strings with at least as many $a$'s as $b$'s. $\def\L#1{{\mathcal L(#1)}}$ $$\begin{align} S&\to EM\mid E\\ M&\to aDM\mid aD\\ E&\to aBE\mid bAE\mid\epsilon\\ D&\to aBD\mid\epsilon\\ B&\to b\mid aBB\\ A&\to a\mid bAA\\ \end{align}$$ The following table should help us understand the strings ...


1

Your question is easy to answer. Take your grammar, and add the following rules: $$ \begin{align*} &S \to T \mid \mathit{Expr} \\ &T \to \mathit{Expr} \end{align*} $$ Your particular grammar, however, does seem unambiguous. Here is how I would try to prove it. First, show the expressions are self-delimiting: no expression is a prefix of another one....


2

A nonterminal $X$ is nullable if you can generate the empty word from it. For example, since $A \to \epsilon$, we see that $A$ is nullable, while since the only production involving $B$ is $B \to b$, we see that $B$ is not nullable. In class, you were shown algorithms for determining which nonterminals are nullable. These algorithms are important for ...


1

Both of your languages are context-free and not regular. The first one can be generated using the following grammar: $$ S \to a S \mid a S b \mid aab $$ The second one can be generated using the following grammar: $$ S \to aaSbbb \mid aabbb $$ You can show that these languages are not regular using the pumping lemma or using Myhill–Nerode theory. Let me ...


2

First, let us notice the following: $$ L(S) = \{ xyz \mid x,z \in \{0,1\}^*, |x|=|z|, y \in L(A) \} \\ L(A) = 0L(B)1 \cup 1L(B)0 \\ L(B) = (0+1)^* $$ Putting everything together, we get $$ L(G) = \{ x\sigma y \tau z \mid x,y,z \in \Sigma^*, \sigma,\tau \in \Sigma, |x|=|z|, \sigma \neq \tau \} $$ In other words, a word $w$ is in the language if there exists $...


Top 50 recent answers are included