# Tagged Questions

54 views

### Challenge on Property of Complement in Language

We have: and M be a finite automata. Suppose d(M) be a deterministic automata that equivalence to M. if $M_1$ and $M_2$ be two finite automata, $M_1 + M_2$ is the finite automata such that the ...
31 views

### Pumping lemma for $a^n b^{2n}$

I have this question and i am not sure and trying to solve in both way that is through diagram and expression: Question : Prove that $a^nb^{2n}$ is not regular. contradiction: ...
37 views

### Proving irregularity using Myhill-Nerode theorem

I'm trying to prove that the following language is irregular using the Myhill-Nerode theorem $$L = \{ w\space\epsilon \{a,b,c\}^* | \#_b(w) > (\#_a(w) + \#_c(w))! \}$$ While it's completely ...
I'm trying to prove that $L = \{ww^R : w \in \{a,b\}^*\}$ ($w^R$ is the reverse of $w$) is not regular using the pumping lemma. Let $p$ be the pumping length and $s = a^pbba^p$. $x = \epsilon$, $y = ... 2answers 41 views ### Regular Expressions Help [duplicate] I need a little help with Regular Expressions. The allowed operations are obviously + (union) , * (Kleene star) and concatenation. I have to write Regex for the following 2 examples. I have tried a ... 1answer 28 views ### Prove a language is Context Free I am working on the following problem and I do make a little progress. Let me state the question first: Prove that the set of strings consisting of$a$'s and$b$'s with an equal number of$a$'s and ... 1answer 38 views ### Name for grammars with rules$A \to uA$Recall that a right-linear grammar is a grammar that consists of rules of the form$A\to uB$, where$A$and$B$are non-terminals and$u$is a (possibly empty) word of terminals. Similarly for ... 1answer 55 views ### Prove or disprove whether the following is a regular language I'm given the regular language L, and w being an element of L. If we remove the w from the language L, will the resulting language be still regular? Well I thought to be true. Since initially is a ... 3answers 54 views ### Prove that this language is not regular (Pumping Lemma) Prove that the following language is not regular. I have no clue where to start. $$L = \{ a^n b^n c^n \mid n \geq 0 \}.$$ 1answer 28 views ### Prove L is not a regular language (A Finite State Automaton cannot accept it) $$\mathscr L = \{x \in \{0,1\}^* \mid \text{there is a } y \in \{0,1\}^* \text{ such that } x = yy\}$$ How can I prove that this is not a Regular language? I tried using proof by contradiction but ... 2answers 57 views ### How to solve pumping lemma questions? I am trying to prove that L = { aNbMaN-M|N>=M>=0} is not regular using the pumping lemma. I am pretty confused how to solve this. What I have so far (which I am not sure is right) is: Assume L is ... 1answer 44 views ### Checking some Regular Expression problems I'm given the alphabet $$\Sigma = {\{a,b}\}$$ I tried to write a regular expressions for presenting the following sets: All strings in $$\Sigma ^ *$$ with: a-) number of 2s divisible by 4 b-) ... 1answer 20 views ### How to prove the following related with regular languages How can we prove the following. If $$\sum$$ is any alphabet and L is any language $$L \subset \sum*$$ Then L*L* = L* ? 0answers 57 views ### Prove the following by using mathematical induction If we define the alphabet such that $$\Sigma = {\{a,b}\}$$ and let$w$be a string over it. I'd like to prove $$( \operatorname{comp}(w))^R = \operatorname{comp}(w^R)$$ where $$w^R$$ and ... 2answers 36 views ### Prove by induction on a string I want to practice proving the following: Given a binary string s, I want to prove$s$has the same number of substrings 01 and 10$\iff$the first and last character of$s$is the same. For ... 1answer 22 views ### How can I show ithat a language is regular? I have a very quick question about regular languages, I think$\{a^{2n}| n\geq 1\}$is regular. I do know that pumping lemma can be used to show something that is not regular. I am wondering what ... 1answer 27 views ### Question About Pumping Lemma used on a FA I am learning about pumping lemma and I am trying to solve a problem. I need to use pumping lemma to show that: the Language L(M) defined by the following machine is infinite. Here is the dfa: ... 0answers 52 views ### This proof in my textbook involving the pumping lemma appears incorrect - is it? It states Let$B$be the language$\{0^n1^n2^n | n \geq 0\}$. We use the pumping lemma to prove that$B$is not regular. The proof is by contradiction. Assume to the contrary that$B$is regular. ... 1answer 39 views ### showing language that is non-regular using pumping lemma I am looking over pumping lemma and the author is using it to show that the language is non-regular. {a^n b^n a^n} = {aba aabbaa aaabbbaaa........} Is there ... 2answers 122 views ### Prove the language$\{a^k b^l : k \neq l \}$is not regular Prove that the following language is not regular: $$L=\{a^k b^l : k,l \ge0, k\ne l\}$$ The problem is that I should use "distinguished states" not the pumping lemma, which is usually used for such ... 1answer 50 views ### Question about equlaity of two language, simple but tricky. I found the following question tricky: If$A$is a language, when will$A^*=A^+? By definition, $$A^* = \bigcup^{\infty}_{i=0}A^i = A^0 \cup A^1 \cup A^2 \cup \cdots$$ $$A^+ = ... 2answers 20 views ### A question about operations on languages. I come across this problem on a book. It states that: for languages A and B, (A\cup B)^* = (A^*B^*)^*. I know that the definition of star closure is \left(\bigcup^{\infty}_{i=1}\right)A^i. But so ... 1answer 42 views ### A correct proof for this pumping lemma example? Given the language L = \{0^{2^n} | n \geq 1\} So, the language contains all strings that have 2^n 0s. First of all I take z = a^{2^p} where p is the constant guaranteed by the pumping ... 1answer 32 views ### Pumping Lemma Squares Proof Explanation I'm looking for some help understand this perfect squares proof using the pumping lemma. Here is the proof: I don't understand how n^2 + k < n^2 + n towards the end of the proof. Would anyone ... 2answers 321 views ### Regular expression and DFA/NFA questions If a language L is generated by a regular expression, then L is recognized by a DFA. I think this is true, because regular expressions describe regular languages, those of which are exactly ... 1answer 60 views ### Are languages regular if their concatenation is regular? Let A, B \subset \Sigma^* be languages. If the concatenation product AB is regular, are A and B necessarily regular? I'm inclined to think this is true since the regular language AB has a ... 1answer 82 views ### Finding Nerode equivalence classes How am I supposed to find the equivalence classes of a Language? What should I think? For instance, having a language$$L =\{a^n b^m \mid n,m \ge 0, (m+n) \bmod2=0)\}$$I can have: [a^n] with ... 0answers 32 views ### Why every regular language is in \text{TIME}(n)? How can I prove that every regular language R has linear time complexity, i.e. every regular language satisfies$$R \in \text{TIME}(n)$$1answer 21 views ### Language regularity implications I have to decide whether this implications are true or false and prove it. Will you help me? L.\{a,b\}^{*} is regular \implies L is regular L.\{a,b\}^{*} is not regular \implies L is not ... 1answer 55 views ### Formal Languages - Prefix on Language Given a language L over an alphabet \Sigma, we say that u,v \in \Sigma^* are prefix equivalent over L, denoted u \sim_L v, if uw \in L \iff vw \in L holds for all w \in \Sigma^*. Is ... 2answers 47 views ### Injective map, that maps context-free languages to regular languages Let \Sigma \neq \emptyset be an alphabet. Is there an injective map f: \Sigma^* \rightarrow \Sigma^* such that for every context-free language L \subseteq \Sigma^* the set f(L) is a regular ... 1answer 71 views ### Prove/Disprove: vwvw=vvww iff \{v\}^*\{w\}^*=\{vw\}^* Let \Sigma be an alphabet and v,w\in \Sigma^*. I'm trying to prove that:$$vwvw=vvww\quad\text{iff}\quad\{v\}^*\{w\}^*=\{vw\}^*.$$I tried to do it by induction, with no success. Any help will ... 1answer 97 views ### Prove the following language is not regular The set of strings of 0's and 1's, beginning with a 1, such that when interpreted as an integer, that integer is prime. I'm assuming the best way to move forward is to use the pumping lemma. I'm ... 1answer 131 views ### Construction of Regular Expression I have the problem of needing to construct a regular expression corresponding to the set of strings of 0's and 1's whose number of 0's is divisible by five and whose number of 1's is even. ... 1answer 199 views ### Prove regular language closed under min and max Given some regular language L, show that L is closed under the following operations:$$\begin{align*} \min(L) &= \{w\mid w\in L,\text{ but no prefix of }w\text{ is in }L \}\\ \max(L) &= ... 1answer 29 views ### Regular languages that are stutter-invariant but not star-free (LTL/FO-definable) I am looking for simple examples and/or general ideas on regular languages (I am interested in finite words and infinite words alike) that are stutter-invariant (a languageL$over an alphabet$A$is ... 1answer 36 views ###$L$is a class of languages that cannot be represented by a regular expression. How to state cardinality of$L$.$L$is a class of languages that cannot be represented by a regular expression. The book says that the cardinality of$L$is$2^{\aleph_0} > \aleph_0$what's the logic behind getting the ... 2answers 41 views ### Let$L$be the language defined by the regular expression$(a \vee b \vee c)(a \vee b \vee c)$1) How does$|L| = 9$? 2)$|L^*| = \aleph_0$? Thank you 2answers 104 views ### Pumping Lemma to show a language is not regular Let$\Sigma = \{a, b\}$. Use the Pumping Lemma to show that$\mathcal L = \{ a^pab^q: p < q \}$is not regular. Not sure how to apply PL here, if someone can give some direction. 0answers 18 views ### How to say “Take result X from the following simultanious calculation and multiply by z” in one equation? If I have a simulataneious equation, for example: { 5x+10y=3 10x+5y=4 } so the person solving the exuation would need to calculate X and Y (1/3 and 2/15 ... 1answer 107 views ### Pumping lemma$L=\{a^ib^j | i \neq j ; i,j \ge 0\}$[duplicate] So, let's have language$L=\{a^ib^j | i \neq j ; i,j \ge 0\}I have to prove that it's not regular. \begin{align} \omega=a^nb^{n+1}=a^{n-1}ab^{n+1} \end{align} \begin{align} x&=a^k\\ y&=a\\ ... 2answers 290 views ### Constructing a finite automata from a subset of its language I am attempting to solve the following problem: LetM=(Q,\Sigma,\delta,q_0,F)$be a deterministic finite automata which accepts$L(M)$, and let$E$be the subset of$L(M)$consisting of all words of ... 1answer 48 views ### Connection of closed subsets of$A^{\omega}$and deterministic Büchi-Automata, Question from Book: Infinite Word by D. Perrin & J.-E. Pin In the Book Infinite Words (homepage) it is proofed that: If$X \subseteq A^{\omega}$, then regarding the Cantor-Topology, the following is equivalent: (1)$X$is closed (2)$X$is recognized by a ... 0answers 48 views ### Expressiveness of finite memory programs Assume we have a simple programming language with while, if, := (assignment), ... 1answer 171 views ### Formal Reduction: Pushdown Automata recognizing context free languages with bounded stack I am studying for an exam in automata theory and I am having trouble solving the following: Consider pushdown automata and context free languages. Show that the following decision problem is ... 5answers 425 views ### A computer's memory is finite, so how can there be languages more powerful than regular? A computer has a finite memory. There are no computers with infinite memory. Therefore the only languages that a computer can process are those whose member strings are finite. As I recall, the ... 1answer 151 views ### Is this language regular? Given$m,n∈Z$, A is a finite alphabet set ,and$L=\{(a^m,a^n)\}^*$is subset of$A^*\times A^*$. Is this language regular ? For example, is$L=\{(a^3,a^7)\}^*$regular ? Here L is not the set ... 2answers 48 views ### Regular composition of non-regular language I've got the following problem: Let's take language$L$. Is it posible that$L$is not regular itself, but it's composition$L\cdot L$becomes regular? I suspect that's correct, yet I ... 2answers 35 views ### Proving irregularity of a language While learning about formal languages, I found the following problem: Let us consider words over the alphabet$\lbrace 0, 1\rbrace ^3$. We say that a word$\langle a_1, b_1, c_1 \rangle \ldots ...
Is the following sound reasoning, and if so, why? Letting $S$ be a language over the alphabet $\Sigma$, $$\bigcup_{i=0}^{\infty}\left(\bigcup_{k=0}^{i-1}S^k\right) = \bigcup_{i=0}^{\infty}S^i$$