New answers tagged

1

This seems impossible if the translator has to be deterministic. Let's clean up the problem and ask the PDA to convert $a^{n+m} b^n$ to $x^m y^n$ (your translator can be converted to such a translator by using a regular transducer). Since your PDA is deterministic, it cannot output anything until it knows whether $m = 0$ or not, which can happen in one of ...


1

On top of what others have said, many modern programming languages come with explicit disambiguation rules, and non-compiler-writers are often not aware of just how often these are applied. Most modern programming languages have a two-level grammar, split into lexical analysis and syntax analysis. The lexical language in particular is almost always based on ...


2

The boundary between context-free and context-sensitive is only determined by one thing: whether or not it can be decided with a nondeterministic pushdown automata. With respect to grammar specifically, most practical programming languages are almost context-free if not context-free, but the context-free/context-sensitive distinction isn't nearly as ...


2

For a detailed discussion how C as standardized in 2011 (see ISO/IEC 9899:2011 – Programming languages – C) diverges from context freeness you might want to look at Jourdan and Poitier, "A simple, possibly correct LR parser for C11", ACM Transactions on Programming Languages and Systems 39:4 (Aug 2017), article 14. And that one assumes preprocessed ...


57

Practically no programming language, modern or ancient, is truly context-free, regardless of what people will tell you. But it hardly matters. Every programming language can be parsed; otherwise, it wouldn't be very useful. So all the deviations from context freeness have been dealt with. What people usually mean when they tell you that programming languages ...


2

Indeed, the requirement that the DPDA accepts by empty stack has some "severe" consequences. Under the standard definitions, an automaton with empty stack is blocked from further computations, as normally one would pop a stack single symbol at each computational step. As a consequence DPDA languages by empty stack are prefix-free: if the accepted ...


1

Regular expressions correspond to a simple recursive definition, which starts with the symbols from some alphabet and extends them with applications of three operators: alternation, concatenation and Kleene closure. So ask yourself: Which of these operators can produce an infinite set? Formal definition: Let $\Sigma$ be a finite set of symbols. Then the set ...


2

I let you verify that the submonoid of $(\Bbb N, +)$ generated by $2$ and $3$ is equal to ${\Bbb N} - \{1\}$. It follows that $$ K = \bigl\{w \in A^* \mid |w| = 2 \text{ or } |w| = 3\bigr\}^* = A^* - A $$ Now $K \subseteq L$ and $L \cap A = \emptyset$. Thus $K = L$.


1

We are provided the language : $$L=\{w| |w| \text{ is prime} \}^*$$ Let us investigate the type of strings in $L$. We see that $L$ has such strings whose length is either zero or can be expressed as a sum of prime numbers. i.e. if $x \in L$ then we have : $$|x| = \begin{cases} 0 \text{ or}\\ \Sigma p_i \text{ where $p_i$ $\in$ Set of all prime ...


2

In fact this follows from a general property of the star operation. When we start with an arbitrary language $L$ of all strings of certain lengths, then the star $L^*$ of that language is always regular. More precisely: Let $A\subseteq \mathbb N$, and $L = \{w\in \Sigma^*\mid |w|\in A\}$. Then $L^*$ is regular. This is a consequence of a property of unary ...


1

You are correct. However we can simplify this a bit: $\epsilon + (a+b)^2(a+b)^*$. The language is all words with length $\neq 1$. Thanks to @Emil Jerabek and @Nathaniel for pointing this out in the comments! (and correcting me multiple times!)


2

You can write your language as a union of simpler languages: $$ \{ a^{i+2} b^i : i \geq 0 \} \cup \{ a^{i+1} b^i : i \geq 0 \} \cup \{ a^i b^i : i \geq 0 \} \cup \{ a^i b^{i+1} : i \geq 0 \} \cup \{ a^i b^{i+2} : i \geq 0 \} $$


1

You can use the word $a^pb^p$, where $p$ is the constant promised by the pumping lemma.


2

Your language is regular. Indeed, the condition $nm \geq 3$ is equivalent to ($n = 1$ and $m \geq 3$) or ($n \geq 3$ and $m = 1$) or ($n \geq 2$ and $m \geq 2$). It is described by the regular expression $$ a (bb)^3(bb)^* + a^3a^*bb + a^2a^*(bb)^2(bb)^*. $$


3

It is regular since $a^*(bb)^* \setminus L$ is regular: $a^*(bb)^*\setminus L = a^* \cup (bb)^* \cup \{a^mb^{2n}|1\leq mn < 3\}$ The last language of the union is finite thus regular.


3

Nondeterministic guess is a non formal term we use for two (or more) possible transitions from the same configuration. When talking about a non deterministic finite automata, if a state $q$ has two different transitions for the character $a$, and I want to show that it accepts a certain word $w$, then I treat the junction at $q$ where $a$ is read as the ...


1

Here are the first few even natural numbers: $$ \begin{array}{r} 0 \\ 10 \\ 100 \\ 110 \\ 1000 \end{array} $$ Here are the first few odd natural numbers: $$ \begin{array}{r} 1 \\ 11 \\ 101 \\ 111 \\ 1001 \end{array} $$ Notice any pattern? You take it from here.


1

Let $L = \{a^nb^na^mbba^{3m} : n,m \geq 1 \}$, which is clearly context-free. Then $$ \operatorname{half}(L) \cap a^+b^+a^+b = \{ a^nb^na^nb : n \geq 1\}, $$ which is not context-free. Hence $\operatorname{half}(L)$ is not context-free. (If $L$ is a unary context-free language then $L$ is regular, and so $\operatorname{half}(L)$ is regular.)


0

Another easy solutions uses the pumping-lemma for context-free languages. Let $L$ be infinite, prefix closed and context free. Then there is an $l$ such that for all $z\in L$ with length at least $l$ there is a decomposition $uvwxy=z$, s.t. $vx$ has length $>0$, $vwx$ hat length $\leq l$ and $\forall i\geq 0: uv^iwx^iy\in L$ (actually, we don't need $l$ ...


0

Usually, when the context of the statement "if $M$ accepts $x$" is in a loop simulating the execution of $M$ on $x$, we just mean to say that if the simulation stopped and $M$ accepted/rejected then do something, otherwise just continue simulating (the more precise way of writing this would be to say "if $M$ accepted after $t$ steps then...&...


7

There is an example, and $L = \{a^nb^na^{2m}b^ka^k \mid n,m,k \in \mathbb{N}\}$ does the trick. We get that $\sqrt{L} = \{a^nb^na^n \mid n \in \mathbb{N}\}$, which is a standard example of a non-context-free language. To elaborate a bit on how to get there: CFLs can express that two numbers are the same, but not that three numbers are the same. So I want the ...


0

In general if you want to prove that a language is CF, even if in this case the solution proposed by Steven is shorter and more elegant, you can see if there is a PDA that accepts it, even though it my be tough not only to find it but also to formally prove it accepts every string of the language.


1

The language $L' = \Sigma^* y\Sigma^*$ is regular and, by the closure properties of regular languages, so is $\Sigma^* \setminus L'$. Then, by the closure properties of context-free languages, $L_2 = L_1 \cap (\Sigma^* \setminus L')$ is context-free (since it can be written as the intersection of a context free language with a regular language).


1

An oracle call is stronger than emulating a TM: it allows you in constant time to solve the task of checking if some $x$ is in the language specified by the oracle. What you saw didn't use oracle machines, since it proved by assuming towards contradiction: It assumed there is a machine $M$, and showed how to use its code in order to build a new machine $M'$ ...


1

Both $L_1$ and $L_2$ are decidable. Hence, they have algorithms $A_1$ and $A_2$ (respectively) that decide them. Try to create a new turing machine (algorithm) using the two algorithms $A_1$ and $A_2$. For example, for the union $L_1\cup L_2$, you can create the following algorithm: run $A_1$ on the input. If it accepted, then also accept. else, run $A_2$ ...


2

Assume towards contradiction that the language is regular. Let a be the "pumping length" given by the pumping lemma. Let $p \geq a+2$ be a prime number. Consider the word: $w=0^p1^p \in L$. By the pumping lemma, it can be written as $w=xyz$ where $|y| \geq 1$, $|xy| \leq a $, $xy^nz \in L \ \ ,\forall n \geq 0$. Consider $w' = xy^0z$. Note that the ...


3

Every language is a union of infinitely many regular languages: $$ L = \bigcup_{w \in L} \{w\}. $$


0

A direct diagonalization argument is very much usable here (even though a somewhat unorthodox choice, as we have "more natural" separating examples available to us). We can construct in a straight-forward way a notation system for context-free grammars, which then lifts to a notation system $(L_w)_{w \in \Sigma^*}$ for the context-free languages. ...


2

Given a normal form grammer $G$ for an infinite prefix-closed $L$, examine the (almost) regular grammer $G'$ obtained by transforming rules of the form $A\rightarrow BC$ into $A\rightarrow B$. I leave it to you to show that $L(G')$ satisfies your requirements.


3

You can write this language as the intersection of two languages: $$ \{ x \# y \mid xy \in L \} \cap \{ y \# x \mid xy \notin L \} $$ I assume you know how to handle the first one. As for the second one, construct an NFA that acts as follows: Start with a DFA for $L$. Guess which state the DFA will be on after reading $x$. Based on this guess, verify that ...


1

Let us start by noticing that $X \to a^+$, $Y \to b^+$, $Z \to c^+$. Furthermore, $A \to a^n X b^n$ and $B \to a^m Y c^m$. Therefore $S$ generates words of the following two forms: $$ a^na^+b^nbc^+ \\ a^+a^mb^+c^mc $$ You take it from here.


2

I would approach this question in this way, (k) in $\mathrm{LL}(k)$ means the number of lookaheads. The grammar of $\mathrm{L}$ here possess non-determinism. For example, if you can only see aaaa then by just looking at the first k symbols, you can't make the decision whether it is aaaa or aaaabbbb. No matter how large the value of k is, there will always be ...


2

Rosenkrantz and Stearns prove in their paper Properties of deterministic top-down grammars that the language $$ \{ a^n b^n : n \ge 0 \} \cup \{ a^n c^n : n \ge 0 \} $$ is not $\mathrm{LL}(k)$ for any $k$ (see page 246). Presumably a similar proof will show that your language is not $\mathrm{LL}(k)$ for any $k$. You mention a confusion between grammars and ...


0

Let's try to simplify your grammar. First, notice that $A$ generates $(00)^*11S$, and so we can get rid of $A$, obtaining $$ S \to 1(00)^*11S \mid 01S \mid \lambda $$ Similar reasoning shows that your grammar generates the language $$ (1(00)^*11+01)^* = ((1(00)^*1+0)1)^*, $$ which is identical to your regular expression. While the reasoning above is informal,...


0

For a practical example of such a language, take a look at the following language: $L = \{<M_1, M_2, w> | M_1 \text{ halts on } w \land M_2 \text{ doesn't halt on } w\}$ It is not in $co-RE$ since the halting problem isn't (there is a reduction from the halting problem to this problem) And for a similar reason it is not in $RE$ (the complement of the ...


1

No, try to think of a counting argument (i.e, the size of each class) in the following way: There are $2^{\aleph_0}$ possible words in the language, hence $2^{2^{\aleph_0}}$ total languages. However, the number of turing machines is bounded by the total possible number of words (since you can encode a TM as a string), hence there are at most $2^{\aleph_0}$ ...


1

If $j \neq i$ then either $j < i$ or $j > i$. Hence you can write your language as $$ \{ a^i b^j : j < i \} \cup \{ a^i b^j : i < j < 2i \}. $$ It suffices to find a grammar for each of these two languages. Such questions have been asked and answered on this site.


1

I had not the enough reputation in this community to leave a comment on @Umamg's answer; so, I try to complete Umang's answer in mine. One way to show that the language $L=\{a^p: \text{p is a prime number}\}$ is not context-free is to use pumping lemma for CFLs in the following way: If $L$ was a CFL, then given an arbitrary long string in this language, say $...


1

what you can do with that Jflap issue is that just remove the q3 from your turing machine and add new state and make an empty transition from all the final state to the new state added, make the new state as final state and change all previous final state i.e. q0, q1 and q2 to non final state your issue with jflap will be resolved here's your required ...


Top 50 recent answers are included