Tag Info

New answers tagged

4

Looking from the final state $q_2$: $$ u(0|1)^* $$ Arrival only via accepting a $1$ from $q_1$ or $q_0$: $$ v1(0|1)^* $$ Joining the start state $q_0$: $$ (0|\epsilon)1(0|1)^* $$ Noting the back loop $q_1\to q_0$, so we can have $q_0\to q_2$ via $1$ or $q_0\to q_1\to q_2$ via $01$ or $q_0\to q_1 \to q_0 \to q_2$ via $001$ etc. accepting $0^*1$: $$ ...


2

Any path from the start state to an accept state is a string in your language, and if you find a loop from a state A back to itself then you can repeat the loop string as many times as you want after you reach A and then if you can reach an accept state from A then this will lead to an infinite family of accepted strings where the loop string is repeated ...


5

This is a very small DFA, so I’d use a fairly ad hoc approach. Notice first that its language is precisely the set of words that reach $q_2$: once it gets to $q_2$, it stays there, and there is no other acceptor state. Thus, we need only see what words get to $q_2$. Clearly we need a $1$ at some point. It can come right away, thanks to the ...


-1

It seems to be part of a normalization for the sake of convenience. The traditional definition would work as well. Citing from [HanWood2004] "The Generalization of Generalized Automata: Expression Automata" Definition 2. An expression automaton A is specified by a tuple $(Q, \Sigma, \delta, s, f )$ , where $Q$ is a finite set of states, $\Sigma$ ...


0

Question. What are the common features of your three problems? Answer. You have to count some parameter modulo $n$ for a certain $n$. For (1), you have to count $|u|_a$ modulo 2, for (2), you have to count $|u|_b$ modulo 4 and for (3) you have to count $|u|$ modulo 3. If you have this in mind, you can easily design a DFA for each situation. I will ...


2

Your answer to 1 is almost correct: It does not accept strings with zero $a$s such as $bc$. And it does not accept for example $acba$. Try something like $$ [bc]^*(a[bc]^*a[bc]^*)^*$$ Based on this, you should have littel problems to find a regex for $4k$ number of $b$s and then $4k+1$ number of $b$s For the third task, first solve "length equals $3$", then ...


1

Spoiler alert. My solutions. 1) $$ L ::= Bc \mid Cd \\ B ::= aBbb \mid \epsilon \\ C ::= aaCb \mid \epsilon $$ 2) $$ L ::= A \mid B \\ A ::= b \mid aAaa \\ B ::= aaba \mid aaBa $$ Notice that the base case of the B recursion is $aaba$, not $\epsilon$. This removes ambiguity.


2

Suppose that the set of all primes is regular. Then it is recognised by a DFA with say $m$ states. Let $p$ be a prime whose binary expansion ends with $m$ zeros and a $1$, so that $$p=\underbrace{\cdots\ \cdots\ \cdots}_{n\ \rm in\ binary}\, \underbrace{00\cdots00}_{m\ \rm zeros}1=2^{m+1}n+1$$ for some $n$. (We know that there is such a prime from ...


1

The decomposition into $xyz$ is dependent on what input string $0^p1^q$ you choose, therefore, $k$ is a function of $p$ and $q$, so you cannot just set $q = k+1$ afterwards. I would choose $0^p1^{(p-1)!}$ for some $p$ prime at least two greater than the pumping length, since then $xy^0z = xz = 0^k1^{(p-1)!}$ for $k<p$. This is possibly not the most ...


3

For the record, there is a very simple proof using the Myhill–Nerode criterion. Let $p_i$ be an enumeration of all primes. Since $0^{p_i} 1^{p_i} \notin L$ while $0^{p_j} 1^{p_i} \in L$ (for $j \neq i$), we see that the words $0^{p_i}$ are pairwise inequivalent with respect to $L$, and so $L$ is not regular. If you really need to use the pumping lemma, let ...


0

HINT: Start with a DFA for the original language $L$, and modify it to get a DFA for the truncated language. The only part of it that you need to change is the set of acceptor (final) states.


0

I'm not sure this'll help, as I'm not very familiar with comp sci, but consider a general discrete example $$x_{k+1} = f(x_k), \quad k=0,1,...,n-1 \qquad (1.1)$$ where $f(x_k)$ determines the next state. Then consider a different discrete case where we have a input variable $a_k$ so that the above becomes $$x_{k+1} = f(x_k,a_k), \quad k = 0,1,...,n-1 ...


0

This fact is absolutely obvious, and the intended induction proof is apt to make it less believable. Hear this: We are given a finite $\{a,b\}$-string. Interchanging all $a$s and $b$s, and then reversing it produces the same result as first reversing it and then interchanging all $a$s and $b$s.


0

Let us prove the result by induction on the length $|w|$ of $w$. If $|w| = 0$, then $w$ is the empty word and the result is trivially true. Suppose that the result holds for all words of length $\leqslant n$ and let $w$ be a word of length $n + 1$. Without loss of generality, we may assume that the last letter of $w$ is an $a$. Thus $w = va$ for some word ...


0

Do it as suggested by mrp but you have to make his automaton deterministic. This is easy, just add a new "dead" state and add transitions from the first 6 states to it with for the symbol that was not yet used on those states. This new state has transitions into itself for both a and b.


1

The language $L$ consists of all strings start start with an $a$, then five $b$'s, then any any number of $a$'s and $b$'s (including none) and four $b$'s at the end. Thus, a DFA that recognises $L$ can be described as follows. The start state only has an $a$-transition to the next state, and the following five states only have $b$-transitions to the next ...


0

Using the state diagram to regular expression algorithm outlined in section 9.2 of Tennents "Software Specification" I was able to come up with the following language. $b^*ab^*aaa^*b(a + bb^*a) + b^*ab^*abb^*a + b^*ab^*aaa^*b(a + bb^*) + b^*ab^*abb^*ab(a + bb^*a) + b^*ab^*abb^*a + b^*ab^*abb^*ab(a + bb^*)$ Verifying this with the diagram shows the language ...


0

There is a standard way to do this, though it is unlikely to give you the most efficient result. First create a non-deterministic finite automaton to recognise the finite language you want. This could consist of one "piece" like the one you have shown for each word - so, for your first question, three pieces: the states in the second would be labelled ...


0

To prove that a certain function is primitive recursive, as you probably know, you need to be able to describe the function using only the basic primitive recursive functions. This gives us a definition that could look like: $$\mathrm{floorlog}(b,x) = \left\{\begin{array}{ll} \mathrm{null}(x) & b = 0 \\ g(b-1, \mathrm{floorlog}(b-1, x), x) & b > ...


3

A DFA has no $\epsilon$-transitions, so this is not a DFA. I would rather called your automaton a nondeterministic finite automaton with $\varepsilon$-moves. Your regular expression $1(11 \cup 0^*)^*$ is correct. Your informal description is almost correct: you should just modify your sentence each $1$ after the first, will be accompanied by at least ...


3

You can be pretty sure that your answer to (ii) is wrong, since (iii) asks you to show that $aabbccc\in L(M)$, and $aabbccc$ doesn’t satisfy the condition in your answer to (ii). Notice that there is only one possible transition from the initial state $q_0$, so any word that is accepted must start with $a$. When that $a$ is read, the stack remains empty, ...


1

Property 2 is immediate from the definitions: $L_{csl}$ is defined as the family of languages generated by a context-sensitive grammar. $L_{cfl}$ is the family of languages generated by a context-free grammar. Every context-free grammar is trivially a context-sensitive grammar, because a context-free grammar is defined to be a context-sensitive grammar that ...


0

HINT: Stack amber plates as they arrive. When a blue plate comes in followed by a *c(hartreuse plate, unstack two amber plates. Throw a tantrum if the amber plates don’t arrive in pairs, or the blue and chartreuse plates don’t alternate properly.


1

Consider that, if you have a DFA which accepts words in $L$, then it can be in one of finitely many states after it reads the first letter - so, to test if a word is in $L\ominus 1$, we just start the DFA at each of the states it could be in after one letter and if it accepts when started in any of these, the word is in $L\ominus 1$ - and, if you know how to ...


1

Let $$ L_0 ={\{ c^n a^m b^p \mid n+m=p,p \geqslant 6}\} = {\{ c^n a^m b^{n+m} \mid n+m \geqslant 6}\} $$ If $L_0$ was regular then, $$ L_1 = L \cap \{a,b\}^* = \{ a^m b^m \mid m \geqslant 6\} $$ would also be regular (since $\{a,b\}^*$ is regular and regular languages are closed under intersection). Similarly, since $\{a^m b^m \mid m \leqslant 5\}$ is a ...


2

Let us choose $w=a^mb^mc^{2m}$ with $m$ is the number of states of your automaton, and apply the pumping lemma you will have: there exists $x,y,z$ such that: $$\left\{\begin{matrix} w=xyz=a^mb^{m}c^{2m}& (1) & \\ |xy|\leq m& (2) & \\ |y|=d\geq 1& (3) & \\ xy^*z\in L_5& (4) & \\ \end{matrix}\right.$$ The equations $(1)$ ...


1

Hint: Split $a^n$ into $\color{blue}{a^n}$ and $\color{green}{a^5}$, that is, consider language $$L = \{\color{blue}{a^n}\color{green}{a^5}b^m \mid \color{blue}{n}\geq m, m > 0\},$$ where the two new letters $\color{blue}{a}$ and $\color{green}{a}$ are just two distinguishable letters $a$, and $\color{blue}{n} = n-5$. For the second language observe ...


3

Have you seen the proof of the pumping lemma? The rough outline goes like this: If $L$ is a regular language, it is accepted by some finite machine $M$ $M$ has some number of states, say $n$ If $L$ contains a string $w$ of $n$ or more symbols, then $M$, in accepting $w$, must go through more than $n$ states, and since it has only $n$, it must go through ...


0

Informally, the pumping lemma states that "In regular languages, every word that's at least length $n$ can be split into $xyz$ where $y$ can be repeated indefinitely." (Hence the "pumping", I presume.) The $|w| \geq n$ constraint simply takes care of the "at least length n" part. If you allowed $w$ to be any length, the pumping lemma wouldn't hold. ...


2

The $\epsilon$-transition $q_0 \to q_4$ from the (former) first automaton to the (former) second automaton would occur somewhere in the word $w$. So far the prefix $u$ of $w = uv$ was consumed, where $u \in L_1$ because $q_0$ is an accepting state of the first automaton. The suffix $v$ of $w$ is now available with the combined automaton at $q_4$ which is ...


1

As you observed, you get an OR relation by doing a disjoint sum, as in your diagram. To get an AND relation, you must take the product of the two automata. The product of $A$ and $B$ has states that are pairs of states, one from $A$ and one from $B$, so that it tracks the states of $A$ and $B$ together. Then it can accept if it is in a state $\langle ...


1

Given the hypothesis that $L$ is infinite, I suspect that $L_1$ and $L_2$ are supposed to be infinite as well. You can actually use the pumping lemma to help you here. Let $p$ be the pumping length for $L$, and let $w\in L$ with $|w|\ge p$. Use the pumping lemma to decompose $w$ as $w=xyz$, where $|y|\ge 1$, and $xy^kz\in L$ for each $k\ge 0$, and let ...


0

Hint: Regular languages are closed under union, intersection, and complement. (see http://en.wikipedia.org/wiki/Regular_language#Closure_properties). So if your language $L$ contains a string $s$, build a regular language that recognizes just $s$ and also a regular language that recognizes $L \cap s^c$, i.e. all strings in $L$ except $s$.


0

The first is ok, the second is more like :


4

Let me show you a systematic approach. Think of each of the state names as an abbreviation for a regular expression corresponding to the set of words that end at that state when starting from the initial state. Since $B$ and $C$ are the acceptor states, we want the expression $B+C$. (I’ll use $+$ instead of a comma for or; I use $\lambda$ for the empty ...


1

Your first conversion is correct. You need to label your initial node in your second automaton. You also need to consider the epsilon-closure when creating new states - e.g. {1,3} should not be a node, as it is possible to reach state 2, from state 1, under an epsilon-transition.


0

Let $A$ be the alphabet. If $A = \{a,b\}$, then $n(a) + n(b)$ is simply the length of the word. Therefore your language is the set of words of even length and $(AA)^*$ is a simple regular expression for it. If $A$ has more than two letters, then a regular expression for your language is $\bigl(C + (a+b)C^*(a+b)\bigr)^*$, where $C = A - \{a,b\}$.


0

Regular languages are closed under intersection and under left quotients$^*$. Therefore, if $L$ was regular, then the languages \begin{align} L_1 &= L \cap a^* = \{ a^k \mid k = 2^n + 273 \text{ for some $n$ }\} \\ L_2 &= (a^{273})^{-1}L_1 = \{ a^{2^n} \mid n \in \mathbb{N}\} \end{align} would be an infinite regular language. You can now ...



Top 50 recent answers are included