Questions about properties of the class of regular languages and individual languages.

learn more… | top users | synonyms

0
votes
2answers
31 views

Kleene closure, concatenation problem

If $L_1 = \emptyset$ , $L_2= \{a\}$ then what is $$L_1\cdot L_2^* \cup L_1^*$$ The answer given is $\{\epsilon\}$ but I think it should be $\{\epsilon,a\}$. My Approach : $L_1^* = \{\epsilon\}$ ...
2
votes
3answers
80 views

Was there an attempt to make reusable regular expressions?

In everyday practice I often encounter tasks which would benefit from being able to define aliases for chunks of regular expressions to reuse them later. Typical examples include: parsing a floating ...
3
votes
0answers
32 views

context free grammar to NFA

I've been given an exercise to solve which goes as follows: generate an NFA from the given CFG, $$\begin{align*}S &\to AB \mid c\\ A &\to aAb \mid c\\ B &\to bBa \mid c\ . \end{align*}$$ ...
0
votes
1answer
31 views

Give an example of a non-regular language $L$ such that $L^*$ is regular [duplicate]

I can't think of an example of a non-regular language $L$ such that $L^*$ is regular. . Any help ?
2
votes
1answer
13 views

DFAs representing these languages

My question is in response to this answer: http://cs.stackexchange.com/a/18614/22902. I'm not completely sure about the etiquette about asking questions regarding year-old answers, but I'm assuming ...
2
votes
1answer
36 views

Finite Automata — Determine if a set is regular

I have been at this for hours. The question is: Prove that the language $A = \{0^kx \mid k > 0, x \in \{0,1\}^*, \text{ and } \#(0,x) \geq k\}$ is regular, where $\#(n, x)$ denotes the ...
2
votes
1answer
103 views

are regular languages closed under division

I am trying to solve this question which appeared in previous exam paper Can someone help me what i am failing to understand For languages $A$ and $B$ define $A \div B = \{x \in \Sigma^{\ast} : xy ...
2
votes
1answer
85 views

regular expression for binary language has at least one 1

So I had an exam in the subject "Theory Of Computation" and one of the questions was to write down a regular expression of a binary language that has at least one (1) , my answer was : 0* 1 0* (0* 1 ...
2
votes
1answer
48 views

How to prove that the Myhill-Nerode equivalence classes for L are the same as for its complement?

Given language $L$, I want to show that its Myhill-Nerode equivalence classes are the same as for its complement $\overline{L}$. I am thinking of constructing a DFA $M$ for the Language $L$ so the ...
0
votes
1answer
27 views

prove decidability and recognizability

I want to prove that for any language $L_1$ described by a Turing machine and any regular language $L_2$, $L_1 \cap L_2$ is described by a Turing machine that its recognizability and decidability is ...
18
votes
3answers
3k views

Can regular languages be Turing complete?

I was reading about Iota and Jot and found this section confusing: Unlike Iota, where the syntactic tree for a string can branch either on the left or on the right, Jot syntax is uniformly ...
-1
votes
0answers
16 views

Theorems to prove non-regularity without pumping lemma [duplicate]

What are some theorems that can be used to show the existence of non-regular languages without using the pumping lemma?
1
vote
1answer
40 views

If pref(L) is regular, does that imply L is regular?

I have this exercise for homework: Say we have a language L. we know that the language pref(L) (all the prefixes of ...
2
votes
1answer
54 views

Help on using the pumping lemma?

I'm trying to prove that a language is not regular. That language is: {w ∈ {a, b}* | amount of a's in w is equivalent to the amount of b's in w, mod 2}. I have an inkling that this language is not ...
-2
votes
1answer
36 views

NFA: Regular Language that starts with ab but does not end with ab?

$L = \{x \in \{a,b\}^* \mid \text{$x$ starts with $ab$ but does not end with $ab$}\}$ I'm having trouble making a table for this NFA. I tried a few sketches out of the diagram and I can post them ...
1
vote
1answer
64 views

How to write a DFA where the second digit is equal to the last digit of binary strings?

I'm having some trouble writing a DFA for the language $$\{w =b_1\dots b_k \in\{0, 1\}^* \mid b \ge 2 \text{ and } b_2=b_k\}\,.$$ What I thought for this is writing a DFA where there are 4 states, ...
1
vote
1answer
28 views

Proving a language is not regular [duplicate]

I need to prove that the following language is not regular $\{c^mb^na^n \mid n>0,m\geq0\}$ But I am not sure how to do that for this particular one. I vaguely understand pumping lemma, but ...
-1
votes
1answer
42 views

Prove a language is regular [duplicate]

I am asked to find Prove that the following languages are regular languages: (a) $\{a^nb^ma^k \mid n\geq3,m\geq1,k\geq1\}$ (b) $\{a^n \mid n\neq3 \text{ and } n\not\equiv2 \mod7\}$ ...
0
votes
0answers
11 views

Proving a language is regular [duplicate]

I am asked to find Prove that the following languages are regular languages: (a) $\{a^nb^ma^k \mid n\geq3,m\geq1,k\geq1\}$ (b) $\{a^n \mid n\neq3 \text{ and } n\not\equiv2 \mod7\}$ ...
-4
votes
1answer
45 views

Show whether the language with almost as many 0 as 1 in every prefix is regular [closed]

This is the exercise: Let A be a language defined over the alphabet Σ = {0, 1} composed by the strings with the property that in every prefix, the number of 0s and the number of 1s differ by at ...
1
vote
5answers
705 views

Show that every infinite language has a non-regular subset

I'm trying to solve this problem: Let $L$ be some infinite language, show that there exists a sub-language of $L$ that is not regular But can this be correct? If I have the language $\{a\}^*$ ...
3
votes
1answer
45 views

The language of any constant-time Turing machine is regular

Suppose we have a Turing machine $M$ so that there is a constant $t$ such that the Turing machine always runs in time $t$ or less. Prove that the language of $M$ is regular. This seems to be a ...
1
vote
1answer
54 views

When using the Pumping lemma, how do I deal with different cases of y?

I want to prove L is not regular:$$L={\{www|w \in \Sigma^*\}}$$ $$\Sigma=\{a,b\}$$ I am sure I can do so using pumping lemma. I used $$ab^pab^pab^p$$as my chosen string but I am stuck. I do not know ...
0
votes
0answers
16 views

Regualr Expression for C comments [duplicate]

I hope you can help me right now, I am working on lexical analyzer for C language, I am bit confuse bout the regular expression of C style comments. a regex which can handle both single and multiline ...
1
vote
1answer
114 views

Show that a regular language L contains only palindromes if and only if all words of length at most 3n are palindromes

This is an extension of a previous question asked by a different user earlier: Let $x, u, v, w, y, x', u', v', w', y'$ be words satisfying $y'x' = xy$. $y'u'x' = xuy$. $y'v'x' = xvy$. ...
2
votes
1answer
36 views

Pumping lemma for 0^n and n>0

When applying the pumping lemma to $L = \{ 0^n \mid n>0\}$ I do the following: $S = 0^p$ $x = \varepsilon$ $y = 0^p$ $z = \varepsilon$ so $S = xyz = (\varepsilon)0^p(\varepsilon)$ For $x y^i z$ ...
0
votes
2answers
47 views

Help designing a Turing Machine

I am faced with the following question: Design a Turing Machine that recognizes the language $L = \{1^{2n+1}\mid n \text{ is a non-negative integer}\}$. Show the state diagram. I started doing ...
0
votes
2answers
71 views

High Level Explanation of the Pumping Lemma

I have a problem that I cannot figure out regarding using the pumping lemma to prove that a language is not regular. I don't understand how I go about proving through contradiction that the language ...
0
votes
1answer
49 views

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

I proved that $$ \{ 0^n 1^{5n} \mid n \geq 0 \}$$ is not a regular language using Pumping Lemma by following way. Solve by contradiction that $ L = \{0^n 1^{5n} \mid n \geq 0 \}$ is regular ...
5
votes
2answers
241 views

Detecting palindromes in binary numbers using a finite state machine

In my first algorithms class we're creating these patterns that are supposed to model a finite state machine. We were given a task to think if we can figure out a way to detect palindromes in binary ...
3
votes
2answers
86 views

If $L$ is regular, must the language $L_1 = \{w : w^Rw \in L\}$ be regular, or may it be non-regular?

The reverse, $w^{R}$, of a string $w = w_1w_2...w_n$ is the string $w_n...w_2w_1$. Suppose that L is a regular language. Must the language $L_1 = \{w : w^Rw \in L\}$ be regular, or may it be ...
3
votes
1answer
58 views

Showing that A' is a regular language

Let $\Sigma = \{0,1\}$, and suppose that $A$ is a regular language. Define $$A' = \{ u \mid \exists a, b \in\Sigma: abu \in A\}$$ i.e., $A'$ is obtained from $A$ by taking every string in $A$ and ...
-1
votes
1answer
40 views

Equivalence of some Automata & Language & NFA

I read some note about Automaton Course. i see this note, that following all is the same. but i think the L(g) is not equal to NFA and regular expression. anyone could help me with defining the ...
3
votes
2answers
42 views

Finding out if languages involving counting and modulo operations are regular

I am having trouble with the regularity of the two following languages: i) $\{0^{n}1^{m}|n,m>0,n-m=0\,mod\,3\}$ ii) $\{0^{n}1^{m}|n,m>0,n+m=0\,mod\,3\}$ To clarify this is stating that the ...
3
votes
2answers
446 views

If both the concatenation of two languages and the second “half” are regular, is the first too?

Given that $L_2$ is regular and infinite and $L_1 \cdot L_2$ is regular, then $L_1$ is also regular. I need some help on getting started on proving this is the case. My intuition is that if $L_1 ...
2
votes
3answers
100 views

Prove that the equal-length concatenation of regular languages is context free

If A and B are regular, then prove that $A@B = \{xy \mid x \in A \text{ and } y \in B \text{ and } |x|=|y|\}$ is always context free. So I'm trying to come up with the proof that looks something like ...
1
vote
2answers
84 views

Show that for any natural number n, there is a regular language that is not recognized by any DFA with at most n final states

Just as the question asks, I am trying to understand the relationship between the number of accept states a DFA has (not necessarily the total number of states) and the languages it can accept. I ...
3
votes
1answer
121 views

Why does this pumping lemma application “prove” that 0*1* is not regular?

Here is a proof that $0^*1^*$ is not regular, even though it is regular. I'm having a hard time figuring out what is wrong with the proof. Assume $0^*1^*$ is regular. Let $p$ be the pumping length as ...
1
vote
1answer
126 views

Can $\{a^mb^nc^n\mid m,n \ge 1\}$ be proved non-regular using the pumping lemma?

$\{a^mb^nc^n\mid m,n \ge 1\}$ intuitively seems like a non-regular language. It looks like the machine needs to remember the number of $b$s (which isn't limited). The pumping lemma can be used to ...
8
votes
3answers
974 views

Union of regular languages that is not regular

I've come across that question : "Give examples of two regular languages which their union doesn't output a regular language. " This is pretty shocking to me because I believe that regular languages ...
0
votes
2answers
89 views

What does it mean to prove that a set of binary integers is regular?

I'm not exactly sure what this question is asking me to do: Show that the set of binary integers (given as strings over $\{0, 1\}$) that are divisible by $3$ is regular, by giving a DFA that ...
3
votes
1answer
111 views

Prove that the language is not regular without using Pumping Lemma

I am practising problems on Regular Languages and I came across this question: Prove that the language $$\{a^m b^n : m ≥ 0, n ≥ 0, m \ne n\}$$ is not regular. (Using the pumping lemma for this ...
0
votes
1answer
37 views

NFA state complexity for the complement of EPAL restricted to a fixed length

I've been having trouble proving the next statement: Let $L_n=\{ww, |w|=n\}$ (the set of equal-length palindromes (EPAL) restricted to length $2n$). Prove that $L^c_n$ can be accepted by an NFA ...
-2
votes
1answer
36 views

Prove that $(L^*M^*)^* = (L\cup M)^*$

I would like to find out how to prove this statement. Thank you. Well I think that I proved one part of the statement, but my proof doesn't really look elegant. My proof of $(L\cup M)^* \subset ...
1
vote
1answer
68 views

Don't understand closure under string reversal

I am trying to learn from http://www.cs.uiuc.edu/class/su08/cs273/lectures/lect_06.pdf #2 and I understand everything except for the 2nd line of delta prime prime function, I having breaking down ...
1
vote
0answers
71 views

Given a non-deterministic Mealy machine $M$, if $L$ is regular, is $M(L)$ regular?

Consider a nondeterministic Mealy machine, $M$, defined as follows: $M = (Q, \Sigma, \Delta, \delta, \tau, q_0)$ where $Q$ is a finite set of states $\Sigma$ is an input alphabet $\Delta$ is an ...
0
votes
1answer
73 views

For two regular languages, why is the set of words from one that don't have a subsequence in the other also regular?

In general, a string $x$ is a subsequence of $w = w_1\dots w_n$ if there are integers $i_1<\dots< i_k$ such that $x = w_{i_1}\dots w_{i_k}$. The subsequence is proper if $k < n$ and $k > ...
3
votes
3answers
207 views

Clearing a Confusion regarding the Proof of equal no of a's and b's not being a regular language

I was wondering about its proof. The direct use of pumping lemma here is not a viability. So a certain teacher of mine proved this with the notion that $a^{n}b^{n}$ being a subset of this language ...
0
votes
1answer
77 views

Show that the regular languages are closed against taking “the second half” [duplicate]

Given $L$ is regular, the proof that $\mathrm{HALF}(L)$ is regular is pretty straightforward to me (e.g., #11 in this link): simply making a NFA and meeting in the middle with 2 original DFAs, the ...
1
vote
2answers
83 views

Proving Regularity of Languages that are 1/k of an already known regular language

There is this question in Kozen, that states if a language is regular then the first half would also be regular. Also I found a material on the internet that extends the thinking saying a language ...