The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
2answers
48 views

If $\{w^k|w\in L\}$ regular implies L regular?

If L is a language and the language $$\tilde{L}:=\{x^k,x\in L, k\in\mathbb{N}\}$$ is regular, does that imply that L is regular? ($|L|<\infty$ gives equivalence) We came across this question when ...
1
vote
2answers
36 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 ...
0
votes
1answer
80 views

Algorithm for checking if regular language has given property

Give an algorithm that will decide (in any finite time) if given regular language $L$ (given by some regular expression) has given property: $$\forall_{x\in L} \exists_{y\in L} \left( \left(x\neq ...
1
vote
0answers
57 views

Proving that language is regular or not regular

Let $L$ be a regular language. Prove that: $L_{+--}=\left\{w: \exists_u |u|=2|w| \wedge wu\in L\right\}$ $L_{++-}=\left\{w: \exists_u 2|u|=|w| \wedge wu\in L \right\}$ ...
3
votes
2answers
104 views

Is $\frac12 L$ a regular language?

Let $L$ be a regular language. Is $\frac{1}{2}L := \left\{ w: \exists_u |u|=|w| \wedge wu\in L \right\}$ regular too? I think the answer is YES. But I don't know how to prove it. I was trying to ...
1
vote
1answer
96 views

Is language of binary representations regular?

Let $bin(n)$ denote binary representation of an integer $n$. Let $L=\left\{bin(n^2):n\in\mathbb{N}\right\}$. Is $L$ a regular language?
1
vote
1answer
64 views

How to prove that given language is not regular?

Prove that $$L=\left\{uvvw\mid u,v,w \in \{a,b,c\}^*\text{ and }v\ne\varepsilon\right\}$$ is not regular a regular language.
1
vote
2answers
142 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 $$
0
votes
0answers
116 views

Chomsky Normal Form solution for a problem

Here is my attempt at CNF, Original: $$ \begin{align*} S &\to 1 A \mid O B \\ A &\to O B O \mid 1 0 \mid \epsilon \\ B &\to A 1 A \mid 0 1 \end{align*} $$ CNF: $$ \begin{align*} S ...
2
votes
2answers
95 views

Giving a regular grammar for the language

I am trying to brush up on my regular grammar knowledge to prepare for an interview, and I just am not able to solve this problem at all. This is NOT for homework, it is merely me trying to solve ...
2
votes
1answer
117 views

Pumping Lemma problem

Apply pumping lemma to each of these and prove that they are not regular. $L = \{ (0^p)(1^q)2 \mid 0 < q < p\}$ $L_2 = \{ (a^p)(b^q)(c^r) \mid p = q \text{ or } q = r\}$ Here my ...
0
votes
2answers
98 views

Regular expression for strings with length not a multiple of 10

Let $P = \{z^n \mid \text{$n$ is not divisible by $10$} \}$. Give a regular expression for this language and then a generalized regular expression that is shorter than the regular expression.
2
votes
1answer
80 views

Is there a problem with this example?

In example $1.14$ on page $51$ (of the book and $64$ of this link), shouldn't the string $01000$ get rejected? However it seems that the first three digits of the string would force it to an accept ...
3
votes
1answer
120 views

Does the Halting Problem apply when evaluating programs that are regular languages?

Here is my understanding of the Halting Problem: It is impossible to write a program H that can determine for any arbitrary program ...
1
vote
2answers
323 views

If $L$ is regular, prove that $\sqrt{L}=\left\{ w : ww\in L\right\}$ is regular

Let $L$ be a regular language. Prove that $\sqrt{L}:=\left\{ w : ww\in L\right\}$ is also a regular language. I suppose I need to modify state machine for $L$ to accept $\sqrt{L}$, but I've been ...
3
votes
2answers
133 views

Is this proof using the pumping lemma correct?

I have this proof and it goes like this: We have a language $L = \{\text{w element of } \{0,1\}^* \mid w = (00)^n1^m \text{ for } n > m \}$. Then, the following proof is given: There is a $p$ ...
2
votes
2answers
266 views

Regular Languages Algorithm?

I need help proving the following question: Let $L$ be any regular language on $\sum{a,b}$. Show that an algorithm exists for determining if L contains any strings of even length. So far, I know ...
1
vote
1answer
193 views

Prove that if $ L $ is a regular language over the alphabet $ Z = \{ 0,1 \} $, then $ L' = \{ax \mid x \in L \} $ is also regular for any a in $Z$.

Prove that if $L$ is a regular language over the alphabet $Z = \{0,1\}$, then $L' = \{ax \mid x \in L\}$ is also regular for any $a \in Z$. I'm not sure how to even begin on this one. If even a ...
3
votes
2answers
93 views

If $L\in REG$ then $M$ has a finite number of distinct rows

Let $L \subseteq \Sigma^{\star}$ and let $M^{\Sigma^{\star} \times \Sigma^{\star}}(\{0,1\})$ an infinite matrix such that for each $x,y\in \Sigma^\star$: $$ m_{x,y}=\begin{cases} 1 & x y\in L\\ 0 ...
2
votes
1answer
91 views

Is $L = \{a^{n+2} b^n | n \ge 0\}$ context free or regular?

Is the language $L = \{ a^{n+2} b^n | n \ge 0 \}$ context free? If so, what is a context free grammar for it? If it is regular, what is a right linear grammar for it?
0
votes
1answer
95 views

The regularity of Markov chains with a threshold

I am studying Paz's "Introduction to Probabilistic Automata", and there is an exercise I cannot solve: Ex. 11, p. 170: Prove that the number of nonregular events of the form $\{x \mid p^A(x) > ...
1
vote
1answer
136 views

How would I go about proving for this NFA?

I am struggling on this one question, where it is asking to define an XOR automata which is defined as an NFA and it is defined as the following: N accepts the string x if the number of distinct ...
1
vote
2answers
50 views

Regular languages question

Describe these languages over $\Sigma={a,b}$ $\Sigma^{*}(a\cup\epsilon)b^*$ $a\Sigma\Sigma^*b\Sigma\cup b\Sigma\Sigma^{*}a\Sigma$ Just making sure I understand some basic concepts... First one ...
3
votes
2answers
381 views

Question about regular languages and finite automata

We say a language $L$ is regular if it is accepted by some finite automaton $M$. I would like someone to clarify this definition. Given a finite automaton $(Q, \Sigma, \delta, q_0, F)$, we define the ...
2
votes
2answers
115 views

Basic regular expressions problem

I'm in an intro to CS theory class learning about regular expressions. I was wondering if people could give me hints as to whether I'm on the right track for these problems. I hope this particular ...
1
vote
2answers
170 views

Prove that any finite set of words is regular. How many states is sufficient for a single word $w_1…w_m$?

DFA Prove that any finite set of words is regular. How many states is sufficient for a single word $w_1...w_m$? For part 2, wouldn't it require M states if the word length is M?
2
votes
2answers
1k views

suffix regular language

Can someone give me an idea how to prove this: suffix(L) = {y | xy $\in $ L for some x $\in$ $\Sigma$ *}. Or suffix is the set of all suffixes of its strings. Prove that if L is regular, then so is ...
1
vote
2answers
237 views

How to prove that the following language is not regular?

This is the following problem that I've been having difficulty on: For this problem, we will show that there are non-regular languages over the alphabet $\{0\}$. The language that will be used is the ...
1
vote
2answers
74 views

Proving this language is regular?

Is $$L =\big\{x^ny^m : |n-m| = 2\big\}$$ a regular language? I can't seem to figure this question out, and i've tried drawing a dfa but I still can't seem to find it. If there is a possible dfa, ...
1
vote
2answers
64 views

Proving a language to be regular

Let $\Sigma_{2}={ \begin{bmatrix} 0\\ 0 \end{bmatrix}, \begin{bmatrix} 1\\ 0 \end{bmatrix},\begin{bmatrix} 0\\ 1 \end{bmatrix},\begin{bmatrix} 1\\ 1 \end{bmatrix}}$ ...
1
vote
3answers
93 views

regular language?

I need help proving whether this language is regular or not. $$L = \big\{ w \mid w \in \{a,b\}^*, n_a(w)\text{ is even}, n_b(w)\text{ is even}\big\}$$ That is, the number of $a$'s is even and the ...
1
vote
1answer
120 views

Question about infinite union of non-regular languages

If none of the languages $L_1$,$L_2$,... is regular, and $L_i \subseteq L_{i+1}$ for each i, is $\bigcup_{n=1}^\infty L_i$ regular? I guess the answer is no for any given languages, but I cannot ...
3
votes
1answer
5k views

Converting to Chomsky Normal Form

I am trying to learn how to convert any context free grammar to Chomsky Normal Form. In the example below, I tried to apply Chomsky Normal Form logic, to result in a grammar, where every symbol either ...
1
vote
2answers
137 views

How can I prove the majority of three languages is also regular if the three languages are regular?

This is a question I've been stuck on recently: Let $A$, $B$, and $C$ be three languages over the same alphabet. Define $\mathrm{maj}(A,B,C)$ to be the collection of all strings $w$ that occur in at ...
1
vote
2answers
83 views

What are the states of this NFA?

I have to realize an NFA that recognizes the language of strings on the alphabet {a, b} ending with: bb, ba, baa. I thought that there must be the following states: $q_0$: the string ends with bb. ...
1
vote
1answer
133 views

Proving this language is not regular

Let $$L = \left\{b^ic^jd^k \mid i \ge 0, j\ge 0, k\ge 0,\text{ if }i=1\text{ then }j=k\right\}\;.$$ I have been trying to get a start on this proof for a long time now with no success. What would ...
2
votes
2answers
276 views

Pumping Lemma Excercise

I am having a really tough time proving the following language is not regular using the pumping lemma. This whole time I have been working on pumping lemma problems, the variable of the power has been ...
2
votes
1answer
256 views

Proving a language is regular or irregular

I am having a really difficult time writing proofs for these problems. I would greatly appreciate any suggestions for a strategy on how to look at such problems and begin writing a proof. Trying to ...
5
votes
2answers
180 views

Pumping Lemma proofs

I am having a hard time writing a Pumping Lemma contradictory proof for the below statements. 1) $L_1 = \{ ww \mid w \in E^* \}$ <--- I don't understand how to read this. This is what I tried: ...
1
vote
3answers
2k views

Determine if a language is regular from the first sight

Is there a way to guess if a language is regular from the first sight? I.e. in order to choose proof methods, I have to have some hypothesis at first. Do you know any hints/patterns? I need this to ...
2
votes
1answer
32 views

Regularity of “middles” of words from regular language

I need some help with the following problem: $L$ - regular language and i have to prove that the language $P$ = {$\alpha$| $\beta\alpha\gamma \in L$, $\beta,\gamma \in (A)^*$} is regular. In other ...
1
vote
2answers
666 views

How to prove by pumping lemma these languages are not regular?

$L_1 = (a^k * b^r \mid k \neq r^2)$ $L_2 = (a ^{\sum_i ^n t} \mid n > 0 )$
0
votes
1answer
221 views

Building a regular grammar from NFA

I'm requested to make a regular grammar from a given NFA. In this NFA, there's a "death state", which means, when getting to it, there's no way back to the rest of the states (a self-loop to the same ...
1
vote
1answer
74 views

Proving or disproving regularity of a language

The question is as follows: If L1 and L2 are not regular and L1 ⊆ L ⊆ L2, then L is regular My intuition says that it's wrong so I've been looking for a ...
0
votes
2answers
100 views

following languages regular or not?

Please help me determine if those languages are regular or not. If not, I'll be glad to get a direction to prove it by contraditiction of the pumping lemma: $L = \{a^n\mathord{*} a^m \mid m \equiv ...
0
votes
1answer
45 views

proving by construction that language is regular

I had this exercise saying the following: $$ L =\{w\mid w = w_1xw_2 \land w_1, w_2, x\text{ are words }\land w_1w_2 \in L_1 \land x \in L_2\} $$ I need to prove that $L$ is regular by defining an ...
2
votes
0answers
283 views

Regular, Context-free, Recursive, Recursively Enumerable Language Relationships

I am currently under the believe that all regular languages are context free, thus all regular languages are recursive, and therefore all regular languages are recursively enumerable. If I am given ...
3
votes
3answers
152 views

Pumping lemma contrapositive

I have a few questions about Pumping Lemma Contrapositive. First of all, how do I choose pumping length $n$? Is it just any constant from the language definition? i.e. I have $L=\{a^kb^gc^hd^j\}$ so I ...
4
votes
1answer
1k views

Myhill Nerode - is language regular or not?

I'm trying to understand how to find equivalence classes of a language to prove its regularity. I think that if I'm able to FULLY understand one example then I will get this topic right. Let's say I ...
0
votes
4answers
109 views

Language over $\{0,1\}$

I am learning about languages but struggling with operations on them. In my book there are some simple examples but how would I for example describe a language over $\Sigma=\{0,1\}$ such that every ...