New answers tagged formal-languages
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 ...
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.
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\}$.
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.
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 ...
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 ...
2
You proved that any finite languages are regular. All the languages that you generated are finite.
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
Equal numbers of a’s on either side, then the middle is replaced by a+b or by ba+.
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.
0
proving kleene closure of DCFL is not DCFL
-4
Here is working code. Don't forget to input your percentage in fractional form (e.g. $0.02$ for $2\%$).
#include <stdio.h>
#define MONTHS_IN_YEAR 12
float monthlyRepaymentAmount(float principalAmount, float interestRate, int numberOfYears);
int main(void) {
//Problem statement variables
float principalAmount; // use int if principal can ...
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 ...
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 ...
0
I believe I can prove that:
a RE using only possessive operators is equivalent to a RE without possessive operators.
any RE can be rewritten to an equivalent RE that uses only possessive operators.
For two expressions $A$ and $B$ to be equivalent means that they define the same language:
$$A\equiv B \implies L(A) = L(B)$$
Let's mark with "$\hat{\ }$" the ...
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
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
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$ ...
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 ...
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$.
0
The class languages recognized by FTMs are the class of regular languages. A FTM can completely simulate a DFA, so each regular language can be recognized by a FTM. On the other hand, if we can prove each FTM recognizes a regular language, we have proved the assertion.
Given a FTM $F$ with the set of states $Q$, we use the Myhill–Nerode theorem to show the ...
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$).
0
Above answers are excellently written. But one other approach would be helpful I think.
We want to prove that if $L(A)$ is a $CFL$ and $L(B)$ is a regular then $L(A/B) = \{w\space|\space wx \in A,\space x\in B,\space w\in \Sigma^*\, ,\space x\in \Sigma^*\}$ is also a $CFL$.
Let's use fact that set of regular languages and set of context free languages are ...
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 ...
0
After days of constantly refreshing this page in hope for an answer today I woke up and my very first thought might be it.
If all states are reachable and it is deterministic this means there has to be a set of inputs where every state will once be reached.
semi-decidable Algorithm:
Validate if DLBA-Encoding and reject if not; # returns 'no' on bogus
...
0
Let w be the shortest word in L with length l. Then the shortest word in $L^2$ has length 2l, but the shortest word in $L^3$ has length 3l. If l ≥ 1 then the sets are different.
Now assume L contains the empty string. $L^3$ is the set of all strings that can be created by taking an element of $L^2$ and adding an element of L. Among many others, this ...
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 ...
0
There is something to be gotten out of the computation.
Either you interpret the final tape contents (and you stop by the "HALT" command, not by going into an accept state, which you do not have), or
you distinguish two states (accept, reject), or
stopping means accept (again by HALT, no accept state) and running forever means reject.
The halting problem ...
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 ...
Top 50 recent answers are included
