New answers tagged formal-languages
0
I'm going to address the second part of the question first, about a "smarter grammar." One improvement that can be made is omitting the rules
$$S \rightarrow Sc \hspace{10px}| \hspace{10px} Sd.$$
Assuming we have made that change, to answer the first part, if the grammar is correct we need to answer two questions.
Does $S$ only generate strings within $L$?...
1
Since you didn't explicitly specify that $S'$ should be a context-free grammar, I'll take the opportunity to mention Boolean grammars, which are a fairly modest extension of CFGs that allow conjunction and negation in rules, in addition to the implicit disjunction of CFGs. The productions have the form
$$A \to \alpha_1 \And \ldots \And \alpha_m \And
\lnot\...
0
If the machine does exacly 5 moves, it reads at most 5 symbols. If after 5 moves it is still going, it does more than 5 moves on a tape starting with that string. So you have to check a finite set of possible inputs (strings of 5 symbols), each for a finite number of steps (5 in this case). So you can always answer "yes" or "no" in finite time, this is ...
0
How about $\{a^{\Sigma(n)} \colon n \ge 1\}$, where $\Sigma$ is Radó's noncomputablr busy-beaver function?
6
Contrary to what you wrote, context-free languages are not closed under complement. See Examples of context-free languages with a non-context-free complements for some examples. As a result, there is no such algorithm.
Also: It's decidable whether $L(S)=\emptyset$, but it's not decidable whether $L(S)=\Sigma^*$. If you could compute the complement, then ...
0
The classes are defined over words of the alphabet such that two words $x, y$ are equivalent if for any word $z$ we have $xz \in L$ if and only if $yz \in L$.
Consider for each $n\in \mathbb{N}$ the class $C_n$ defined as $$C_n = \{x : \#_x(b) \geq 1 \text{ and } \#_x(a) -\#_x(b) = n\}.$$
Note that for each word in this class we can add exactly the strings ...
0
Assume $L$ is context free, thus it satisfies the pumping lemma. Call the constant of the lemma $p$. Pick the string $\sigma = a^p b^p c^{p^2} \in L$, and $\lvert \sigma \rvert = p^2 + p \ge p$. By the pumping lemma, you can write $\sigma = u v w x y$ so that $\lvert v w x \rvert \le p$, $x, y$ not both $\epsilon$, such that for all $k \ge 0$ it is $u v^k w ...
0
Yes. Say $N$ is the constant of the pumping lemma, and consider $\sigma = a b^N c^N \in L$ and $\lvert \sigma \rvert = 2 N + 1 \ge N$. By the lemma, you can write $\sigma = \alpha \beta \gamma$, such that $\lvert \alpha \beta \rvert \le N$ with $\beta \ne \epsilon$ such that for all $k \ge 0$ it is $\alpha \beta^k \gamma \in L$. Now $\beta$ must be composed ...
0
You can recognize (but not decide) $L_1$ (essentially checking it ends "0", if so simulating $M$ on $x$ by a universal Turing machine $U$, otherwise reject).
$L_2$ is essentially the complement of the language of $U$, which is not recognizable.
$L$ is not recognizable. If it was, say by a Turing machine $R$, you could run $R$ in parallel over $\langle M, w,...
0
By Rice's theorem, it is undecidable if $M$ accepts a language with a non-trivial property (there are languages that have the property and others that don't). "Includes a string starting 101" is a non-trivial property.
2
You can always take $n = 1$ for any string in your language...
1
This proof uses both construction and knowledge of closure properties of regular languages.
First, we know that regularity of languages is closed under the reversal operation, see proof of Thm. 4.2 here.
We can then define an operation named chop such that:
$$
\text{chop}(L)=\{w|aw \in L\}, \text{ where } a \in \Sigma,
$$
We can construct an NFA for ...
2
Assume a finite state machine. Since the state machine is finite there are n != m where $a^n$ and $a^m$ end up in the same state. So $a^nb^n$ and $a^m b^n$ both end up in the same state, so are either both in L or both not in L, which contradicts the definition of L.
1
Suppose that $B$ were regular. According to the pumping lemma, there exists an integer $p \geq 1$ such that every word $w \in B$ of length at least $p$ has a decomposition $w = xyz$, with $|xy| \leq p$ and $y \neq \epsilon$, such that $xy^tz \in B$ for all $t \geq 0$.
Pick some Fibonacci number $F_n$ such that (1) $F_n \geq p$ and (2) $F_{n+1} - F_n > p$....
3
A regular grammar corresponds directly to a finite automaton, mapping each non-terminal to a state. So this question is equivalent to asking how to minimize the number states in a finite automaton. Unfortunately, minimizing NFAs is hard. See, for example, Gregor Gamlich, 2007.
1
I's easy to understand the pumping lemma if you see where it comes from.
Assume L is regular, so there is a finite state machine. Say that state machine has p-1 states. That's where the p comes from.
Now parse any string of length p or more that is in the language. Since there are only p-1 states, somewhere within parsing the first p characters of the ...
0
To use closure properties, suppose $L$ is regular. Then it's complement, $\overline{L}$ is also regular, and so is $\overline{L} \cap \mathcal{L}(a^* b^*) = \{ a^n b^n \colon n \ge 0\}$, but that one is known non-regular. Contradiction.
1
Have a good look to the answer you link to. It specifies the language that is generated using two numbers $k,\ell$. These numbers guarantee that the two parts are different without ever knowing where the middle of the string exctly was. I will try to explain.
We have to find (or better, guess) a position in $x$ such that the same position in $y$ carries ...
1
There is a big difference between $\{ xy ∣ |x| = |y|, x = y \}$ and $\{ xy ∣ |x| = |y|, x \ne y \}$. In the first one, we need every symbol in $x$ to be the same as the corresponding symbol in $y$. For inequality, it suffices that at least one symbol in x be different from the corresponding symbol in $y$. The two cases are not symmetrical.
Checking that ...
0
The lemma states that all strings longer than $p$ can be subdivided into $x y z$ with $\lvert x y \rvert \le p$ and $y \ne \epsilon$ so that for all $i \ge 0$ $x y^i z$ belongs to the language. This means that $0 < \lvert y \rvert \le p$, obviously. If you take a "pumped" string, i.e. $x y^i z$ for $i > 1$, the resulting string is longer than $p$ and ...
2
$A_1$ is regular, since regular languages are closed under intersection and complement, and $A_1 = A \setminus B^{R} = A \cap (B^{R})^{c}$. To show that the reverse $B^{R} = \{x^{R} : x \in B\}$ of a regular language $B$ is regular, take some deterministic finite state machine $M$ with language $B$. Construct a new nondeterministic finite state machine $M'$ ...
1
I will assume, based on the way you presented the problem, that you only care about errors where single characters are replaced with other single characters—as opposed to merging two adjacent characters into a similar-looking single character, splitting a single character into two similar-looking adjacent characters, etc.
One option would be to build a ...
1
DCFL is subset of CFL. But with this we can't say all operations which are closed for CFL are also closed for DCFL. I will give you example :
Suppose we have 2 DCFL whose Union is CFL but not DCFL.
When we are considering Union from CFL, product of union is inside CFL. But when we are considering DCFL ,product after Union is not inside DCFL.
I hope problem ...
2
Just show that after processing $0^n$ and $0^{n’}$ with n != n’ you must have reached two different states. (Which is easy: In one state, processing $1^n$ leads to an accepting state, in the other state it doesn’t). Therefore there is no finite set of states.
Or you just take the pumping lemma, p arbitrary large, and w = $0^p 1^p$. Which makes y = $0^k$ ...
0
One way would be to show an isomorphism between strings and ordered sets, then the result is a direct consequence of properties of set cardinalities (namely that $|A \times B| = |A|\cdot|B|$ for any two sets $A$ and $B$).
Let's assume that you don't want to do that (for a start it's probably more work to do it properly - but very quick to do it in a hand-...
1
The numbers (2n over n) are a quickly growing sequence.
Assume you have a state machine for L. After processing say (20 over 10) 1's you are in a state that is accepting (obviously because (20 over 10) 1's are in the language L), and further 1's go to non-accepting states until there are a total of (22 over 11) 1's. So you have an accepting state $S_{10}$, ...
3
A unary language (i.e., a subset of $0^*$) $L$ is regular iff the set $S = \{ n : 0^n \in L \}$ is eventually periodic. In particular, if $L$ is regular then either $S$ is finite or $S$ has positive density (in the following strong sense: $|S \cap [n]|/n$ converges to a positive number). However, in your case the set $S$ is infinite yet has density zero.
In ...
1
Suppose for contradiction that $L = \{0^{2n \choose n} : n \in \mathbb{N}\}$ is a regular language. Then by the definition of a regular language there exists a deterministic finite automaton (DFA) that recognizes $L$. Let $D$ be such a DFA and let $|D|$ denote the number of states in $D$.
Choose an $n$ such that ${2n \choose n} > |D|$ and define $S = 0^...
4
Your attempt was pretty close! But I think that this is the way to go for you
$$S \rightarrow a a a a X$$
$$X \rightarrow a X a \mid b b$$
The way that these rules come together forces there to be the four necessary $a$'s at the start and then it's a matter of matching $a$'s with $b b$ in the middle.
So after that, it's a question of making a CFG that ...
0
You can always build a PDA with just one state for any CFL (just work through building a PDA from a grammar using top-down parsing), the result of your construction will accept essentially anything.
0
Given a DFA for $L$, let $\mathcal{Q}$ be the set of states that are reachable from the start state. Construct an NFA-$\epsilon$ by adding a new start state $S$ and adding an $\epsilon$-transition from $S$ to each state in $\mathcal{Q}$. You can see the new NFA-$\epsilon$ recognizes $L'$.
0
Your conclusion that $L’$ is a concatenation of two regular languages is wrong.
$L’$ is basically the set of suffixes of all the strings in $L$. Try to prove it for the prefixes and use the “closed under reverse operation” property of regular languages.
Hint for prefix language: make some special states as final state in the DFA of a regular language.
3
The languages of all palindromes is context-free.
That does not implies that any language that contains only palindromes is context-free. For example, many language over the unary alphabet $\{a\}$ are not context-free. In fact, they can even be non-context-sensitive or undecidable. Note that any word over a unary alphabet is a palindrome.
In particular, ...
2
What you write is a snippet out of a recursive descent parser, one way of writing a program that parses a context free language. It is modelled on a PDA, specifically a LL(1) one. The stack is implicit in the recursive calls your parser does. Recursive descent is popular as it easy to write by hand (some tricks are needed to handle ambiguous constructs, like ...
0
Be careful, $L_1 \subseteq L_2$ with $L_2$ regular doesn't always mean that $L_1$ is regular. For one example, pick $L_1 = \{a^n b^n \colon n \ge 1\}$ (usually the first language proven non-regular), $L_2 = \mathcal{L}(a^* b^*)$ (defined by a regular expression, thus regular).
1
You need to use one intersection operation. It is a known closure property that if two languages $A, B$ are regular, then the intersection $A \cap B$ will also be regular. In this case, $A$ is the given regular language. The other one, $B = \textrm{Even}(\Sigma^*)$, is the language of all even-length strings. The language you want to prove is the language ...
1
Could you make a FA that accepts all and only even-length strings? What do you know about the intersection of two regular languages?
0
Use closure properties. Define homomorphisms $h_1$ and $h_2$ as follows:
$\begin{align*}
h_1(x) &= \begin{cases}
x & x \in \Sigma \\
\sigma & x = A \text{ (a new symbol)}
\end{cases} \\
h_2(x) &= \begin{cases}
x & x \in \Sigma \\
\tau & x = A
\end{cases} \...
0
Let's write formally what $L$ and $\overline{L}$ are:
$$L=\{\langle M,w,b \rangle| (b=0 \wedge M(w) \mbox{ halts}) \vee (b=1 \wedge M(w) \mbox{ does not halt}) \}$$
$$\overline{L}=\{\langle M,w,b \rangle| (b=1 \vee M(w) \mbox{ does not halt}) \wedge (b=0 \vee M(w) \mbox{ halts}) \}$$
The latter is confusing, so let's rearrange it:
$$\overline{L}=\{\langle ...
1
Practically speaking, the C++ threading (memory) model is directly inspired by the Java Memory Model, and C followed. Hans Böhm was closely involved with the process and has a great resource list. (*)
You'll quickly note that your dates are pretty optimistic - this memory model did not exist in 1985 when the first C++ implementations were created. There's ...
2
There are many approaches for concurrency, with different tradeoffs. We have threads with shared mutable state (e.g., SRC-style threading). We have coroutines (like Go). We have actor models with independent processes communicating via message passing (like Erlang or E).
I would put CSP on a different level. It's not the same sort of thing. The form of ...
Top 50 recent answers are included
