# Tagged Questions

Regular languages are formal languages which are recognized by a finite automaton. It is equivalently the languages which are expressible as a regular expression. In addition to these two, there are several other equivalent definitions.

58 views

### Regular expression with xor [duplicate]

Can anyone help me with this question: I know i asked a similar question not a while ago but i'm not able to understand how its possible. If anyone could give me a lot of examples instead of an ...
24 views

### Regular expression problem

I have this question and no clue how to solve. Thanks for your help I need to build the regular expression matching this language $$L=\{ 0^m~1^n | (m+n) \pmod 3 = 1 \}$$
222 views

### Help with proving a language is regular (Sipser problem 1.49a)

I am working through Sipser's Introduction to the theory of computation on my own, so I don't have access to a teacher. Hopefully you can help me! Giving hints is highly appreciated. This question is ...
107 views

### Prove that whenever L is a regular language so is HasPrefix(L)

For a language $L$ over an alphabet $\Sigma$, deﬁne the language $\operatorname{HasPrefix}(L)$ as follows: $$\operatorname{HasPrefix}(L) = \{xy\mid x,y \in\Sigma^*, x \in L, xy \in L, |y|> 0\}$$ ...
62 views

### How to prove that a language L is not a regular language?

Given the following question: Prove that the following language is not a regular language: A language L in alphabet $\Sigma = \{a, b\}$ where every word ...
67 views

### Is this correct way to prove that { $uv$ $\mid$ $u$ and $v$ are strings over $(0,1)$ & $|u| = |v|$ } language is not regular?

I proved this using Pumping Lemma in the following way, Taking $p$ as pumping length then let us take a string $S$ where, $|u| = |v| = p$ Now according to pumping lemma $S$ can be split into three ...
77 views

### How to prove that $\{ 0^n 1^{5n} : n \ge 10000 \}$ is not a regular language?

I proved that $$\{0^n 1^{5n} : n \ge 0\}$$ is not a regular language using Pumping Lemma by following way. Solve by contradiction that $L = \{ 0^n 1^{5n} : n >= 0 \}$ is regular language. ...
24 views

### If $R$ is a regular language and both $L - R$ and $L ∩ R$ are context-free then $L$ is context-free

If $R$ is a regular language and both $L - R$ and $L ∩ R$ are context-free then $L$ is context-free I have to prove or give a counterexample. I know the closures properties of CFL, however, this ...
55 views

### Show that the language is not regular using Myhill-Nerode Theorem

I saw that similar questions have been answered on this site, but I've been unable to translate those answers to my problem. $$L=\{ww^R\mid w \in \{a,b\}^*\}$$ This is what I tried: BWOC, assume ...
90 views

### Question about formal languages, quotient operator L1/L2.

I come across this problem: Consider the following regular languages: $L1=\{a^*b^*c^*\}$ over the alphabet $A=\{a,b,c\}$ and $L2=\{( a b | b b | a )^*\}$ over the same alphabet as above. Find the ...
51 views

### Prove regular languages closed under operation by changing alphabet?

Suppose we have the following language operation: $Duplicate(L) = \{Duplicate(w)|w \in L\}$ where if $w=w_1w_2\ldots w_n$ $Duplicate(w) = w_1w_1w_2w_2 \ldots w_nw_n$. It is simple to construct a DFA ...
35 views

### Is this language regular? $\{0^n 1^m \mid m \ne n\}$, I don't understand the direct proof by pumping length

There is a direct way to prove it: If $p$ is the pumping length and we take the string $s = 0^{(p)}1^{(p+p!)}$, then no matter what the decomposition $s = xyz$ is the string $xy^{(1+p!/|y|)}z$ will ...
44 views

156 views

22 views

### converting to regular expression

{w | w can be written as $0^k l 0^k$ for some $k \geq 1$ and for any $l$ in ${0,1}*}$ i.e. 00010111000 can be written as 0^3 10111 0^3 How can I convert this description into a regular expression? ...
51 views

### Regular language that has a string that cannot be pumped.

This is a question from a past exam. Consider the language $F = \{w | w \in 0^{*}1^{*}\}$ that is kown to be regular. a) Show that if string $w$ is chosen to be $0^p1^p$, that is a member ...
64 views

### Nonregular languages that satisfy the pumping lemma at different strengths

There are three versions of the pumping lemma that I've seen, each one stronger than the last (as in it fails on some non-regular languages that pass the weaker ones) The three versions are as ...
84 views

### equivalence class for language in Theory of automata

we say x,y is equivalent to language L, if for any $z \in L$ we have: $xz \in L \Longleftrightarrow yz \in L$. for $L= (ab \cup aab)^*$, what is the equivalence class for L? my professor ...
94 views

### disprove $L = \{ a^nb^n\mid n \geq 0 \}$ is not a context-free using pumping lemma for CFL

I am writing something about pumping Lemma. I know that the language $L = \{ a^nb^n\mid n \geq 0 \}$ is context-free. But I don't understand how this language satisfies the conditions of pumping lemma ...
300 views

### CFG with reverse strings

I've been trying to figure this out for a while, and I'm at a total loss: Write a context-free grammar that generates the language $\{x y\ |\ x$ is a string over $\{a,b,c\},\ y$ is a reverse of ...
30 views

### Why is $\left\{a\right\}^*\cap L(A)=\emptyset$? where $\delta(q,a)=q$

I am trying to solve this particular problem from Automata Theory by Ullman, Hopcroft, it is as shown below : Let $A$ be a $DFA$ and $a$ be a particular input symbol of $A$, such that for all states ...
28 views

### find a regular expression

find a regular expression for w such that it does not contain $aab$ , where w is the strings of $a$'s and $b$'s . ans: I know how to draw the same question with $aab$ , but cant understand how to ...
49 views

### Regular Expression Similarity Check

I was solving Formal Language and Automata Theory for a competitive exam, whence I came upon this following question: The regular expression 0*(10*)* denotes same set as: 0(0+10)* (0+1)10(0+1) ...
12 views

### Find a state machine or a regex that accept the following language description

The alphabet of the language L is {a, b} and there has to be an even number of both a's and b's but no other restrictions apply. I've been at this for over an hour, drawing state machines that lead ...
122 views

### Show that the language is not regular using the pumping lemma.

I have to show that the language $L = \{ a^k b^k \mid k > 0 \}$ is not regular using the pumping lemma. I have done the following: Let $i \geq 1$ $$x = a^i b^i \in L$$ $$|x| = 2i \geq i$$ ...
32 views

### Check if it is regular language

I have a language $L = \{ a^i b^j c^k \mid i \geq 1 \land j \geq 1 \land k \geq 1 \land (i \neq j \lor j \neq k) \}$ and how to check if it is regular language? I tried using pumping lemma for ...
92 views

### PDA and Some language Grammar inference

L1={$w^*$| w=x and $x \in \Sigma^*$} L2={$ww^R ww^R$| $w \in ( \Sigma + \Sigma)^*$} L3={$w | w=xy, x,y \in \Sigma^*$, y is a substring of x} a) there is a PDA(push down automata) that accept ...
60 views

### Regular Language and Unknown Operation

I read the $L$ is a Regular language. Define $L'$ as following: $$L'=\{a_2a_1a_4a_3\ldots a_{2n}a_{2n-1}\mid a_1a_2\ldots a_{2n} \in L\}.$$ why $L'$ is Regular? any hint or idea would be highly ...
49 views

### A CFG Grammar for One Language

Suppose : $w_1,w_2 \in \{a,b\}^∗$ and $L=\{w_1w_2 \mid w_1,w_2 \in \{a,b\}^* \land n_a(w_1)=n_b(w_2)\}$ $n_a$ is number of $a$'s and $n_b$ is number of $b$'s. This is a Entrance Exam question. I ...
72 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 ...
101 views

### disproving union of infinitely many regular languages

I want to disprove the following statement: "if $L$ is the union of infinitely many regular languages, then $L$ is guaranteed to be a regular language." I don't know where to start. Any hint will be ...
57 views

### “The regular languages over $A$ are the homomorphic pre-images in $A^*$ of subsets of finite monoids.”

I'm trying to understand the statement: The regular languages over $A$ are the homomorphic pre-images in $A^∗$ of subsets of finite monoids. which appears in the Wikipedia article on free ...
348 views

### Pumping lemma proof of $L = \{a^nb^m \mid 0\leq n<m\}$

Prove the following language is not regular using the pummping lemma $L = \{a^nb^m \mid 0\leq n<m\}$ I tried solving this problem what I don't think I was able to reach an accurate proof. But this ...
43 views

### Frequency of Words in Document

I'm trying to figure this out: Would someone care to explain how one would go about using this function? More specifically, I don't understand the interval part, how does one count the intervals? ...
61 views

### NFA for $L = \{ w \in \{a,b,c\}^* : \text{at least one symbol appears only once in }w \}$

Write an NFA to recognize the language $$L = \{ w \in \{a,b,c\}^* : \text{at least one symbol appears only once in }w \}.$$ I'm not quite sure how to do this question. I don't know how to keep ...
109 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: ...
86 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 ...
32 views

### Prove that a language is not regular.

I want to ask how to prove the following language is not regular using closure properties. I tried to use pumping lemma but I find the proof itself shaky. I'd appreciate if you can help. The ...