1
vote
1answer
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 ...
0
votes
0answers
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: ...
1
vote
0answers
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 ...
1
vote
2answers
68 views

pumping lemma: ww^R not regular

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 = ...
2
votes
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 ...
0
votes
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 ...
1
vote
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 ...
1
vote
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 ...
1
vote
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 \}.$$
0
votes
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 ...
1
vote
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 ...
1
vote
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-) ...
1
vote
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* ?
1
vote
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 ...
1
vote
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 ...
0
votes
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 ...
0
votes
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: ...
2
votes
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. ...
0
votes
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 ...
0
votes
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 ...
1
vote
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^+ = ...
1
vote
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 ...
2
votes
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$ $0$s. First of all I take $z = a^{2^p}$ where $p$ is the constant guaranteed by the pumping ...
1
vote
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 ...
0
votes
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 ...
2
votes
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 ...
1
vote
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 ...
1
vote
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)$$
1
vote
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 ...
0
votes
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 ...
3
votes
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 ...
0
votes
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 ...
1
vote
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 ...
0
votes
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. ...
0
votes
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) &= ...
1
vote
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 language $L$ over an alphabet $A$ is ...
0
votes
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 ...
0
votes
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
0
votes
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.
0
votes
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 ...
1
vote
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\\ ...
1
vote
2answers
290 views

Constructing a finite automata from a subset of its language

I am attempting to solve the following problem: Let $M=(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 ...
0
votes
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 ...
2
votes
0answers
48 views

Expressiveness of finite memory programs

Assume we have a simple programming language with while, if, := (assignment), ...
3
votes
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 ...
7
votes
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 ...
0
votes
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 ...
2
votes
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 ...
1
vote
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 ...
1
vote
2answers
135 views

Infinite union of finite unions

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 $$