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 ...
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 ...
3
Suppose $S_c$ is context free. Then let $p$ be the pumping length and choose $s = 0^{2p}0^p1^p0^{2p}$ in $S_c$ will satisfied the pumping lemma. Thus, we can break $s$ in to $uvxyz$, with $|vxy| \leq p$ and $|vy| \geq 1$. And for any $i$, $uv^ixy^iz$ is a string in $S_c$. Now, we have three cases for above conditions:
$vy$ contains all 0s and these 0s can ...
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.
3
$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'$ ...
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 ...
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 ...
2
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 ...
2
Could you make a FA that accepts all and only even-length strings? What do you know about the intersection of two regular languages?
2
The answer is no. Some context-free languages are inherently ambiguous: every context-free grammar defining a language of this kind will be ambiguous. An example is
$$\{a^ib^jc^k \mid i = j \text{ or } j = k\}$$
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$ ...
2
You can always take $n = 1$ for any string in your language...
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
First we assume for the $S_3$ is decidable and let TM $R$ be the decider for $S_3$. With $R$, we can test whether $M$ writes symbol $``3"$ on the third cell of its tape at some point. If $R$ indicates that $M$ doesn't write $``3"$ on the third cell, reject because $\big \langle M,3 \big \rangle \notin A_{TM}$. If $R$ indicates $M$ writes symbol $``3"$ on the ...
1
Let us define 4 non-terminals $X_{00}, X_{01}, X_{10}, X_{11}$ and the start variable $S$. The rules are as follow:
\begin{align}
S &\rightarrow X_{00},\\
X_{01}&\rightarrow \epsilon,\\
X_{00}&\rightarrow 0X_{10},\\
X_{00}&\rightarrow 1X_{10},\\
X_{01}&\rightarrow 0X_{11},\\
X_{01}&\rightarrow 1X_{00},\\
X_{10}&\rightarrow 0X_{00},...
1
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\...
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$....
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 ...
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
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}$, ...
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^...
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 ...
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 ...
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible
