New answers tagged

0

The two-tape machine has a transition function $\delta$ which takes the current state, $s$, and the symbols from the current positions on the two tapes, $t_1$ and $t_2$, and tells what the new state $s'$ is. Define a transition function that gives $\delta(s, t_1, t_2)$ one value when $t_1=t_2$, and a different value when $t_1\ne t_2$. Then the machine will ...


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

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

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

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

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-...


0

A general strategy could be something like: Put a $c$ at each end of the string. Keep interchanging the left $c$ with the symbol to the right of it, and the right $c$ with the symbol to the left of it, until there are no more symbols between them. (While you move from one end of the string to the other, you don't need to remember any details about the end ...


0

The answer is yes. Given a context-free grammar generating a language $L_1$ and a regular language $L_2$ given by some finite automaton, one can effectively construct a context-free grammar generating the language $L_1 \cap L_2$. Now, given a context-free grammar, one can decide whether the language it generates is empty or not.


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.


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\}$.


0

I suppose the problem asks that if $q, w \in X^{+}$ (note that $q = \varepsilon$ gives a regular language) are given, we should consider the language $$ L = \{ qw^jq^k \mid j, k \in \mathbb N, j > k \mbox{ or $j$ is odd } \}. $$ i) This language fulfills the conclusion of the pumping lemma with $N := |q| + 2\max\{|w|,|q|\}$. To show this let $qw^jq^k \...


0

The construction of DFAs via (left) derivatives seems not to be as commonly known as it should be; see this paper. The left derivative of a language $L$ over an alphabet $\Sigma$, with respect to a symbol $a$, is $$D(L,a) = \{w\in\Sigma^*\mid aw\in L\}.$$ For a regex $r$, let $L$ be the language described by $r$; then $D(r,a)$ is a regex matching $D(L,a)$; ...


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$.


0

Hint. if you know how to handle the complement, you can use the formula $K \cup L = (K^c \cap L^c)^c$, where $L^c$ denotes the complement of $L$.


0

If your definition of DFA allows for multiple accept states (usually it does), then the simplest way is to take the same DFA for the intersection, with the only difference being that your set of accept states should contain any state in which either machine 1 was accepting or machine 2 was accepting. In this case, that means any state with either a "3" or 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^{...


0

Your explanation is a little hard to follow, but it appears to be basically correct. The key point is that $|xy|\le n$ and $|y|\ge 1$, so that $y=q^k$ for some $k\ge 1$. But then $$xy^iz=q^{n+(i-1)k}w^ne^{2n}\;,$$ and $n+(i-1)k+n=2n+(i-1)k$ is equal to $2n$ if and only if $i=1$. Thus, if $i\ne 1$, then $xy^iz\notin L$.


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 ...



Top 50 recent answers are included