Tagged Questions

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

learn more… | top users | synonyms

1
vote
1answer
25 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
26 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 ...
0
votes
1answer
46 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
26 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
35 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
10 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\}$ ...
-2
votes
0answers
29 views

Why is $L_1-L_2$ regular for any two regular $L_1,L_2$? [on hold]

How do I show that for any two regular languages $L_1,L_2$, their difference $L_1 - L_2$ is also regular? I tried to solve this but I'm not sure my solution works.
-4
votes
1answer
43 views

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

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 ...
-2
votes
0answers
22 views

Proving that a particular subset of some regular language is also regular [duplicate]

Let's say a language $A$ is a regular language over alphabet $\{a,b,c\}$. How can I prove that the subset of $A$ that contains at least one $c$ is a regular language?
1
vote
5answers
673 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
43 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 ...
0
votes
1answer
45 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
92 views

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

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
33 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
40 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
67 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
39 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
208 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
81 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
39 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
40 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
439 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
96 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
80 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
110 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
116 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
883 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
86 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 ...
2
votes
1answer
102 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
35 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
65 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
65 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
72 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
177 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
73 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
80 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 ...
3
votes
1answer
80 views

Find a regular language that becomes non-regular if you cut away the middle third of all words

Let $A$ be a regular language, let $A'=\{xz\}$ such that for some $y,|x|=|y|=|z|$ and $xyz\in A$. Show that $A'$ is not necessarily regular language. This is an excercise of Sipser, I've no idea how ...
0
votes
2answers
52 views

Show that the language of words with even sum of positions of a letter is regular

Let $\Sigma=\{a,b\}$, and let $S(a)$ be sum of the positions of $a$ of string $S$. I want to prove $$L=\{S\in \Sigma^{*} \mid S(a)=0(\bmod 2)\}$$ is regular. What I was thinking is to do somehow keep ...
1
vote
0answers
38 views

What is regular about regular languages? [duplicate]

I am new to automata theory. I am well aware of the definition of regular language in automata, that is "a language is called a regular language if some finite automaton recognizes/accepts it" [MS]. ...
0
votes
1answer
55 views

Can the definition of regular languages be simplified?

Wikipedia says The collection of regular languages over an alphabet Σ is defined recursively as follows: The empty language Ø is a regular language. For each a ∈ Σ (a belongs to Σ), ...
2
votes
2answers
76 views

Language to Construct Finite State Transducer

I am attempting to write a Finite State Transducer module in OCaml, because I think it's a good exercise, which is because I have been teaching myself Natural Language Processing. You typically ...
-2
votes
1answer
61 views

How to write this regular expression

Consider the language over the alphabet $\sum= \{a\}$ containing strings whose length is either a multiple of 2 or 3 (including the empty strings). Writing a regular expression for this language
2
votes
1answer
38 views

Describing explicitly the MyHill-Nerode classes created by a language

I want to practice proving a language is regular or not using the MyHill-Nerode theorm, but for that I need to be able to describe the classes. Here's my practice attempt: For the language ...
0
votes
3answers
434 views

Problem understanding DFA & NFA equivalence in Theory of Computation

Before asking this question,I had gone through Equivalence of NFA and DFA - proof by construction but my question is a bit different from that. I was reading Michael Sipser's ...
5
votes
1answer
91 views

Infinite non-regular decompositions of regular languages

The title pretty much says it: I'm interested in examples of infinite families of non-regular, pairwise disjoint languages whose union is regular. When is this the case? Or, from a different ...
0
votes
1answer
44 views

Is there a PDA for every Type 3 Grammar?

we learned that for every type 2 grammar G exists a PDA A with L(A) = L(G). But does for every type 3 grammar G exist a PDA A_G with L(A_G) = L(G)? I think it does, because type 2 grammar is a subset ...
3
votes
1answer
125 views

Generators of families of langauges?

From Wikipedia's definition of regular langauges The collection of regular languages over an alphabet $Σ$ is defined recursively as follows: The empty language $Ø$ is a regular language. ...