New answers tagged

1

I'm not an expert, but I try to answer your question with an order, and if I will say something wrong, the people can improve my answer. In general, is possible to use the State elimination method to convert a "Deterministic state automata" (DFA) to a regular expression (RE). From the theory, we know the information below If a language is regular, ...


3

Below a nondeterministic automaton for the language of all strings where the one-but-last letter is an $a$. If we make it determinsitic using the standard construction half of the states will be unreachable. You ask, why does this happen? Look at the initial state $0$ of the original automaton. It has a loop for both $a$ and $b$. That means that in the ...


2

If the construction method supports "negative" regular expression operators, such as set intersection or set difference, it's likely that the method will produce useless states. For example, Brzozowski's method, when given the expression $\left(a \cup b\right)^* \setminus \left( a \left( a \cup b\right)^* \right)$, will likely produce something ...


0

It is not clear if you actually want to construct an automaton for some language, however I can provide some help with understanding the given ones. The first automaton is a bit complicated. The language it recognizes should be, in regular expression form, $$((ab)^\ast (ba)^\ast)^\ast (a + b + \varepsilon)$$ where $\varepsilon$ denotes the empty word. The ...


0

Let the automaton have states $Q$, initial state $q_0$, accepting states $F$, and transition function $\delta$, and suppose that $|Q| = n$. Denote the language that it accepts by $L$. Suppose that $xy^iz \in L$ for $i = 0,\ldots,n-1$. Denote $p_i = \delta(q_0,xy^i)$. We consider two cases: The states $p_0,\ldots,p_{n-1}$ are all different. In this case, $Q =...


0

Suppose that $w = ncm$, where $n \neq m^R$, say $n$'th $i$-th letter from the left, $\sigma$, differs from $m$'s $i$-th letter from the right, $\tau$. Then $$ w \in \Sigma^{i-1} \sigma \Sigma^* c \Sigma^* \tau \Sigma^{i-1}, $$ where $\Sigma = \{a,b\}$. Conversely, every $w$ of this form is in your language. You take it from here.


0

This answer is for the original version of the question, in which "$k$" was missing. Your language contains all non-empty words. Indeed, if $w \neq \epsilon$ then you can write $w = nm$, where $m = \epsilon$ and $n = w \neq \epsilon = m^R$. In contrast, if $\epsilon = nm$ then $n=m=\epsilon$ and so necessarily $n=m^R$.


1

In order to show that $f$ is regularity preserving, it suffices to show that $f^{-1}(U)$ is eventually periodic for $U = \{ n : n \equiv b \pmod{a} \}$, where $a$ is a prime power (here we are using the Chinese remainder theorem and the fact that the eventually periodic sets are closed under intersection). For $f(n) = 2^n$, we consider two cases: If $a = 2^...


1

Hint:


0

I'll explain my thought process behind thinking about this problem here: -> With inequalities, I first think at the equality constraint. So I assume n = m+3 -> Now, n is always 3 more than m. -> I split the problem further. I think to myself okay, let's have one production handle equal production of a and b. -> How many more b's do we need after ...


1

The best way is to learn is to look at examples, and see how they work. One of the simplest "real" context-free languages is $\{\; a^mb^n \mid n = m \;\}$ Its grammar is $S\to aSb\mid \varepsilon$. Now add in steps, the extra 3, and the more than ... $\{\; a^mb^n \mid n = m+3 \;\}$ $\{\; a^mb^n \mid n \le m+3 \;\}$


0

As you mention, if $n$ was fixed, then this is not too difficult to prove. So, the idea would be to show that in fact, $n$ can be bounded a-priori, depending only on $A$, and not on $x$. To this end, consider some word $x\in \Sigma^*$, and suppose $x^m\in A$ for some $m$. Let $k$ be the number of states in some DFA $D$ for $A$ (e.g., minimal DFA). Suppose $m&...


1

It looks like you missed the paragraph for induction right before the Example 4.19 or figure 4.9 and the repetitive application of that induction. INDUCTION: Let $p$ and $q$ be states such that for some input symbol $a,$ $\ r =\delta(p,a)$ and $s = \delta(q,a)$ are a pair of states known to be distinguishable. Then $\{p, q\}$ is a pair of distinguishable ...


0

(a) Let $\Sigma$ be the alphabet of $L$ and $\Sigma^*/\equiv_L$ the set of equivalence classes of words over $\Sigma$ according to the equivalence relation $\equiv_L$. Define the DFA to have one state for each element of $\Sigma^*/\equiv_L$ (we could think of the states as the classes themselves). Define the initial state to be the class of the empty word $\...


0

It occurred to me after I made this post that I could store the states in a linked list format: typedef struct stateRecord { struct stateRecord *next; size_t state; size_t startIdx; size_t endIdx; } stateRecord;


1

The basic idea is that if a regular language is infinite, then it contains a word of infinite length. Indeed, the pumping lemma shows that the set of lengths of words in the language contains an arithmetic progression, and every arithmetic progression contains a composite integer. We can check whether the language accepted by an NFA is infinite as follows: ...


Top 50 recent answers are included