Hot answers tagged

2

It is true that $\overline L$ is context-free, but that does not help you because the context-free languages are not closed under complement. So you need a different start. Hint: Write $L$ as $\{a^mb^n\mid 1\le m<n\} \cup \{a^mb^n\mid 1\le n<m\}$.


2

When you have two context-free languages and grammars generating them, there is an obvious way to create a grammar that generates their union. If the given grammars are non-ambiguous and the languages are disjoint, the new grammar will also be non-ambiguous. All your languages are given as unions (the or-condition for $M_2$ is essentially the same as a ...


1

Something like this: Edit. The two numbers are written in inverse binary notation and you may need to add an extra zero in the front. For instance, suppose you want to add $22$ and $13$. In binary notation, $22$ is $10110$ and $13$ is $1101$. In inverse binary notation, $22$ is $01101$ and $13$ is $1011$. Add $0$ at the end of $01101$ and $00$ at the end ...


1

I agree with your answer: the first two words aren’t in $L(G)$, and the third has a unique derivation (and parse tree). Thus, the correct answer is None of these. The grammar is simple enough that we can identify the language. There are only two possibilities for the first step in a derivation. Suppose that we begin by applying the production $S\to BC$. We ...


1

Let $ S \subseteq \mathbb{N} $ not be $ RE $. Take $ L = \{ a^n \ | \ n \in S \} $. Then $ L $ is not $ RE $. You can also construct explicit examples of such sets, like $ L = \{ a^n \ | \text{ The } n^{\text{th}} \text{ Turing machine halts on all inputs} \} $. To go even further, any infinite set has subsets which are not $ RE $. Let $ A \subseteq \...


1

Your pumping lemma argument for $ L $ makes sense, with the exception that you switch between using $ p $ and $ n $ for the pumping length. The same word doesn't work for $ L' $ though - your word can be split into $ x = \epsilon, y=0, z=0^p1^p $. Then $ xy^iz = 0^{p+i} 1^p $ is in $ L' $ (since it has the prefix $ 0 $ which has more $ 0 $s than $ 1 $s). ...


1

A string us in $L^*$ if and only if it is the concatenation of zero or more strings that for some fixed $k$ consist of $k$ occurrences of $a$ followed by $k$ occurrences of $b$. Thus the string first of all must consist only of $a$'s and $b$'s, and must start with an $a$. We can use run length encoding to describe a string of this form, replacing the string ...


1

The language $L_4$ is not context-free. Indeed, if it was, then $L_4 \cap \{a,b\}^* = \{ ww \mid w \in \{a,b\}^* \}$ would also be context-free. But it is not: see for instance this answer by Brian M. Scott.


1

I'll assume that the question is "is there any derivation involving $A$"? First you need to know which nonterminals can unfold to any word at all. You can find this by fixpoint iteration: start with an empty set, and whenever there's a production $B::=s_1\cdots s_k$ where each $s_i$ is either a terminal or a nontermial you have already identified as fully-...


1

Let $L = L_1 - L_2 = \{a^pb^qc^r \mid p,q,r > 0, p \not=r\}$ and suppose that $L$ is regular. Then the language $a^+bc^+ - L = \{a^pbc^p \mid p > 0\}$ would also be regular, which is not the case. Thus $L$ is not regular.


1

Let $A$ be a finite alphabet and let $L$ be any language of $A^*$. Then $L$ is accepted by the countable automaton $\mathcal{A} = (A^*, A, \cdot, 1, L)$, where the set of states is $A^*$, the initial state is the empty word $1$, the set of final states is $L$ and the transition function is given by $u \cdot a = ua$, for any $u \in A^*$ and $a \in A$.


1

A derivation in $G_1$ can stop only when the production $S\to\epsilon$ is applied. This means that if the derivation ever uses $S\to 1A$, it must eventually use $A\to 1S$, so as to have an $S$ to delete. Here are some possible derivations: $$\begin{array}{ccc} S&\Rightarrow^{n_1}&0^{n_1}S&\Rightarrow&0^{n_1}1A&\Rightarrow^{n_2}&0^{...


1

The language the automaton accepts is supposed to consist of all strings that contain at least three as -- not only some of them. The second of the automata you show fails to accept baaa -- there's no transition that will match the initial b. Since the language accepted by the second automata does not include baaa and baaa is a string that contains at ...


1

This depends to some extent on the terminology used in your course. However a DFA, as I understand the term, must have exactly one transition from every state for each letter. This is not the case in your second example so it is not a DFA. Your second example is however an instance of a non-deterministic finite automaton. You will quite likely prove in ...



Only top voted, non community-wiki answers of a minimum length are eligible