Tag Info

Hot answers tagged formal-languages

7

The same "argument" would show that $\mathbb{N}$ is finite since it's the union of finite sets $$\mathbb{N}=\{0\}\cup\{0,1\}\cup\{0,1,2\}\cup ...$$ The point is that knowing that a given property is preserved under a given operation does not mean that it's preserved under "infinite iterations" of that operation.

5

Your exam question makes very little sense. The obvious reading would be this: Let $M$ and $N$ be two Turing machines. Why is it not possible to prove that $M$ and $N$ compute the same function? More precisely: It is not the case that for all Turing machines $M$ and $N$ it is provable that $M$ and $N$ compute the same function. Well, this is quite ...

4

Clearly not. Let $A=\{a\}$ and $B=\{aa\}$. Now, $A\cap B = \emptyset$ so $(A\cap B)^* = \{\epsilon\}$ but $A^*\cap B^*=B^*=\{a^{2i} : i \in \mathbb{N}\}$ (all strings consisting of an even number of $a$).

3

Just pump up $(M+1)$ $y$'s. Now you get $xy^{M+1}z=a^{(M+1)j+M-j}=a^{M(j+1)}$. Since $M$ is a product of two primes, $M(j+1)$ is a product of at least 3 primes, so $a^{M(j+1)}\notin L_1$, which proves $L_1$ is not regular by the pumping lemma.

3

I'm not sure what $L1, \dots, Lk$ are since you did not define them. The easiest way is probably that of starting with a DFA for $L$ and constructing a NFA for $drop(L)$ (hint in the spoiler below). Then it should be easy to show that: If $w \in drop(L)$ then the NFA accepts $w$: use the definition of the function $drop$ to conclude that there must be a ...

3

Can you use a rule that looks like $S \rightarrow A_1A_2\dots A_iS \mid B_1B_2\dots B_iS \mid Z_i$, where $i \ge 2$? No. Grammar rules consist of explicitly given finite strings of terminals and non-terminals on each side of the arrow, and a grammar may contain only finitely many rules. The first restriction rules out the "for all $i\ge 2$" part of your ...

2

The unique prefix of the empty word $e$ is $e$, and it does not start with $b$. Therefore $e$ satisfies the condition "no prefix of $e$ starts with $b$" and hence $e$ belongs to $L$.

2

Equal numbers of a’s on either side, then the middle is replaced by a+b or by ba+.

2

The idea is to start with a grammar for the related language $L'_2 = \{a^ib^j \mid 2j \leq i \leq 3j\}$: $$S \to a^2Sb \mid a^3Sb \mid \epsilon.$$ We want to force at least one production of the form $a^2Sb$ and at least one of the form $a^3Sb$. There are many ways of doing that. The simplest, probably, is to force one of these productions to be the first, ...

2

You need to keep doing it an infinite number of times before you reach any infinite languages. So your proof will involve transfinite induction. As Wikipedia says: Transfinite induction is an extension of mathematical induction to well-ordered sets, for example to sets of ordinal numbers or cardinal numbers. Let P(α) be a property defined for all ...

2

You proved that any finite languages are regular. All the languages that you generated are finite.

2

Here is yet another proof. It is known that the number of integers at most $n$ which are the product of two primes is $o(n)$, see for example this answer, which gives the asymptotic $\frac{n\log\log n}{\log n}$. This means that your language is infinite yet has vanishing asymptotic density. This is impossible for a regular unary language.

2

The subset of all palindromes in L is obviously not usually regular, take the simple example $a^*ba^*$ where the subset of palindromes $a^nba^n$ is not regular. Assume you have an FSM for L (that is an FSM describing and defining L). You can take that FSM and use a simple algorithm to determine if w is in M: Given a state S, define succ(S, a) as the state ...

1

As all words of length $>1$ and only consisting of a's should be contained in L2, there is a simple finite automaton that recognizes it. So your attempt at using the pumping lemma is futile, as the pumping lemma only helps you prove that a language is irregular if it is, and doesn't tell you anything about languages that are regular. Maybe I'm also ...

1

According to the Fundamental Theorem of Arithmetic, any integer $>1$ can be written as a product of one or more primes (in a unique way). So, it seems that your language can be simplified as $\{a^n\mid n\geq 2\}$.

1

There is an alternative to the “pumping” lemma which I find easier: After each possible input, determine the set of continuations that would complete a string of the language. You can use each of those sets as a state in the finite state machine for the language, so if there is a finite number of those sets then the language is regular- if there are ...

1

Here is one result in the direction you're looking into: Suppose that $A,B,C$ are languages such that $A$ is a non-regular subset of the regular language $C$, and $B$ is disjoint from $C$. Then $A \cup B$ is non-regular. For the proof, consider the intersection of $A \cup B$ and $C$. Details left to the reader. The question you link to concerns the ...

1

Using the accepted answer by @David Richerby -> I think what we have to do is modify the DFAs that recognize L1 and L2. Let L1 alphabet Σ1 and L2 alphabet Σ2, let Σ = Σ1 ∪ Σ2 let's say we have DFA for L1 called M, For M DFA add a extra state called y and for all the letters in Σ but not in Σ1 add a transition from all the states of M to state y. then ...

1

Pushdown automata do not necessarily halt. They are not forced to read input each step, they can also do so-called $\lambda$-instructions where the tape is not advanced. Then we can have an infinite loop at a certain tape position. Likewise, linear bounded automata may loop, and do not always halt. However, they can be simulated by a Turing machine, which ...

1

Let $S$ be the list of all prefixes of words in $L$. Create a DFA with a state $q_s$ for each $s \in S$, and an additional sink state $q_\bot$. The starting state is $q_\epsilon$, and a state is accepting if it corresponds to a word in $L$. When at a non-sink state $q_s$, upon reading $\sigma$, move to $q_{s\sigma}$ if $s\sigma \in S$, and to $q_\bot$ ...

1

Given that, I would expect that for any reasonable model of computation, if $f : A \rightarrow B$ and $g : B \rightarrow C$ are computable, then $g \circ f : A \rightarrow C$ should be as well. Let's say our model is quadratic time computation. If $f$ is the function which maps a string of length $n$ to a string of $n^2$ zeroes, then $f$ is computable in ...

1

I'm assuming by $\lambda$ you mean the empty word and by $n_0(w)$ the length of a word. The proof for the first part is not correct: You argue that every word in $L^2$ has length at least $2$ and every word in $L^3$ has length at least $3$. From that it does not follow that every word in $L^3$ is longer than every word $L^2$, because there could also be a ...

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