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

learn more… | top users | synonyms

-1
votes
1answer
16 views

Context-Free Languages

S → AB | C A → aAb | ab B → cBd | cd C → aCd | aDd D → bDc | bc How can I prove that this language is regular or not? I need your help. It also has two ...
-1
votes
1answer
31 views

Use the pumping lemma to show that the language is not regular [on hold]

I am working on this problem : Use the pumping lemma to show that the language $\{0^n 1^{n} \mid n ≥ 1\}$ is not regular. May someone give me some suggestion about how to solve this problem?
0
votes
2answers
54 views

Draw a DFA that accepts ((aa*)*b)*

A homework question asks me to a draw a DFA for the regular expression $((aa^*)^*b)^*$ I'm having trouble with this because I'm not sure how to express the idea of $a$ followed by $0$ or many $a$'s ...
8
votes
2answers
164 views

Regularity of unary languages with word lengths the sum of two resp. three squares

I think about unary languages $L_k$, where $L_k$ is set of all words which length is the sum of $k$ squares. Formally: $$L_k=\{a^n\mid n=\sum_{i=1}^k {n_i}^2,\;\;n_i\in\mathbb{N_0}\;(1\le i\le k)\} $$ ...
0
votes
1answer
48 views

Proving a language isn't regular using the pumping lemma

Let the language $$ L = \{ a^nb^m : m,n \text{ has the same integer-quotient, (ignoring the remainder) } \} $$ Show that $L$ isn't regular using the pumping-lemma. Let's assume by contradiction ...
1
vote
0answers
22 views

is {a,b}* a regular language? And How to know a language is regular or not without using pumping lemma [duplicate]

I still confuse what is a regular language. I read some books, i know if language likes (a^n b^m| n,m>0), it will be regular language since n and m are not related. I know using pumping lemma can ...
-1
votes
1answer
27 views

union of two equivalence classes (Myhill–Nerode theorem) [on hold]

Let a language, $L$ such that the equivalence relation, as defined in Myhill–Nerode theorem has $4$ equivalence classes; $A_1, \ldots, A_4$. Let $S = A_1 \cup A_2$. Is $S$ always regular? ...
-1
votes
1answer
60 views

Does every infinite recursive language contain an infinite regular subset? [duplicate]

My intuition is telling me that this is not the case. But I am having trouble formulating a proof for this.How do I prove it ?
1
vote
1answer
42 views

Proof that a language is not regular using pumping lemma

I have a language $L$ that I think is not regular: $L = \{w\in \{0,1,...,9\}^* \; | \enspace w \enspace \text{is a decimal representation of a number divisible by 3}\}$ I'm using pumping lemma in my ...
-3
votes
1answer
38 views

What is the minimal states for the language DFA?

Let the language $$L = \{ w: \text{ for any prefix } u \text{ of } w : \left|\#_o(u) - 2\cdot \#_1(u) \right| \le 2 \}$$ What is the minimal number of states for a DFA, accepting $L$? ...
2
votes
1answer
32 views

Prove that regular languages and context-free languages aren't closed under $Perm(L)$

Let the operation $$Perm(L) = \{ w | \exists u \in L \text{ such that } u \text{ is a permutation of } w \}$$ Prove that both regular languages and CFLs aren't closed under $Perm(L)$. I've tried ...
3
votes
3answers
142 views

Show that regular languages are closed under Mix operations

Let $L_1, L_2$, two regular languages and the operations: $$Mix_1(L_1, L_2) =\{ a_1b_1a_2b_2\ldots a_nb_n | n\ge 0 \land a_1,a_2,\ldots ,a_n,b_1,b_2,\ldots ,b_n\in\Sigma\\ \land a_1a_2\ldots a_n\in ...
-1
votes
1answer
49 views

DFA for regular language [on hold]

I need to construct a DFA which accepts the following language: $$ L = \{w \in \{a,b\}^{\ast}\mid \#_{a}(w) \bmod 3 = \#_{b}(w) \bmod 2\} $$ I have no clue how to solve this issue. Can you please help ...
0
votes
1answer
36 views

What is the minimal number of states for the DFA?

Let the regular expression $R = ((a^*\cup \emptyset \cup \varepsilon^*)^*b)^*$ above $\Sigma = \{a,b,c,d\}$. What is the minimal number of states for a DFA accepting this regex? $1$ $2$ $4$ $5$ ...
0
votes
1answer
21 views

Identity productions in regular grammar

If a grammar is of the following form (i.e. all its productions are), is its language regular? $B → a$ - where $B$ is a non-terminal in $N$ and a is a terminal in $Σ$ $B → aC$ - where $B$ and $C$ ...
-2
votes
0answers
20 views

From NFA machine diagram to a Regular Expression

I am attempting to give a regular expression for a NFA (non-deterministic finite automata) machine by using the step-by-step node removal technique. I introduced a new start node and a new final ...
0
votes
1answer
21 views

Handling dead state in NFA to DFA conversion

I want to convert below NFA into DFA: I prepared below tables and finally the NFA: NFA However I feel I am wrong here, since original NFA does not have any transitions defined for state C ...
1
vote
1answer
48 views

Can the concatenation of two non-regular languages be regular?

Can anyone give an example of two non-regular languages $A, B \subseteq \{0, 1\}^∗$ for which the language $AB$ is regular?
-1
votes
1answer
45 views

Prove Language Is Union of Fninitely Many Arithmetic Progressions [closed]

So, you see in the image the question and its answer (proof below the black line). I get the entire proof until the last formula. It basically says that if length of a string is larger than number of ...
-2
votes
0answers
16 views

Show language of binary sums is not regular [closed]

Let $\Sigma = \{0, 1, +, =\}$ and $$ ADD = \{x = y + z\mid x, y, z \in \Sigma^* \text{ and $x$ is the sum of $y$ and $z$}\} $$ Where addition is interpreted as binary addition. For example, the ...
3
votes
2answers
60 views

Proving regular languages are closed under a form of interleaving

I've got the following definitions: $$\mathrm{Interleave}\,(x,y) = \{w_1\dots w_n\mid w_i\in\{x_i,y_i\} \text{ for }i=1, \dots, |x|\}$$ when $x$, $y$ and $w$ are words with $|x|=|y|$ and $w_i$ means ...
2
votes
1answer
36 views

prove that a language is context free given a regular language

R is a regular language over $\Sigma=\{0,1\}$ $Sub(R)=\{0^i1^j \mid \exists w\in R.|w|=i-j \}$ I need to prove that Sub(R) is context free. I know that the quotient of a context free language with a ...
-1
votes
1answer
40 views

pumping lemma for $L=\{a^n b^m c^k \mid n = m \vee m\neq k\}$ [duplicate]

Using pumping lemma, how can I prove that $L=\{a^n b^m c^k \mid n = m \vee m\neq k\}$ is not regular?. If I choose $w= a^m b^m c^m$ and pump up with $i=2$, if have $a^m=1 b^m c^m$ but the string is ...
1
vote
1answer
30 views

Rational subsets of a monoid

In "Rational Set of Commutative Monoid", S. Eilenberg and M.P. Schützenberger define the class of rational subsets of a monoid $M$ as the least class $F$ of subsets of $M$ such that satisfy the ...
-2
votes
1answer
67 views

Convert RE to DFA [duplicate]

I've been trying to convert a regular expression to a non-deterministic finite automata (NFA) first using Thompson's construction, giving: , which looks correct. I am then using subset ...
3
votes
1answer
39 views

Is the language of all $a^n$ for which $n$ has an even number of digits in 10-base system regular?

Is the language $ L = \{a^n ~| ~n \text{ has even number of digits in 10-base system}\} $ regular? My approach: let the $ p $ be from the Pumping Lemma. Chose the smallest $ n $ which has even number ...
1
vote
3answers
101 views

Understanding definition of NP

In my lecture notes, the definition of the class NP is given as: A language $L$ is in the class NP, if there exists a turing machine $M$ and polynomials $T$ and $p$ such that: For every input $x$, ...
0
votes
2answers
72 views

Verification wanted: Show the language $L=\{0^m1^n \enspace | \enspace m \neq n\}$ is not regular [closed]

$$L=\{0^m1^n \enspace | \enspace m \neq n\}$$ I saw that this exact question exists elsewhere, but I couldn't understand what was being said there. My question does not mandate the use of the Pumping ...
0
votes
1answer
52 views

Proving that $L=\lbrace{ab^{n}ba^{n}|n\geq1}\rbrace$ is not regular with pumping lemma

I'm trying to understand the pumping lemma for regular languages and would like to prove that $L=\lbrace{ab^{n}ba^{n}|n\geq1}\rbrace$ is not regular. My suggestion is as follows: Assuming ...
4
votes
1answer
109 views

Can we check in polynomial time if the language of a DFA is closed against Kleene star?

I was wondering if there is a polynomial time algorithm to test whether a DFA recognizes a star closed language ( which is if $A=A^*$). I think that yes, but I do not have an idea to do it.
5
votes
2answers
31 views

Is relative regularity distinct from regularity?

Let $L$ and $G$ be languages over a finite alphabet $\Sigma$. $L$ is regular relative to $G$ if $L \subseteq G$ and there is a finite automaton that accepts every input in $L$, and rejects every input ...
-1
votes
1answer
32 views

Prove a Language is Regular [duplicate]

For a language $L\in\Sigma^*$ we define $$ L^*=\{w\mid \exists k\in \mathbb{N}\cup\{0\}, ∃x_1,...,x_k\in L \ (w=x_1...x_k) \} $$ Let $L$ be a regular language over some alphabet $\Sigma$. Prove that ...
1
vote
2answers
75 views

Prove if given language is regular or not

$$L = \{x^iy^jz^k \mid i \le2j\text{ or }j \le 3k\}$$ To Prove: If given language is regular or not. I know that it is not a regular language but I am not able to come up with the string which I can ...
0
votes
0answers
20 views

Prove that $L_x$ is a regular language [duplicate]

Let $L$ to be a regular language. $L_x = \{y | \exists x,z \text{ s.t } xyz \in L \text{ and } \left|x\right| = \left|z\right|\}$. Prove that $L_x$ is regular. Basically, if $w$ is a word in ...
1
vote
1answer
28 views

How to explain a language with modulo conditions is regular? [duplicate]

I don't want to create a duplicate question of How to prove a language is regular?, I only want to know what is a good and simple way to explain why a language like $\qquad \displaystyle L = \{w \in ...
1
vote
0answers
78 views

If $L$ is a regular language then so is $\sqrt{L}=\{w:ww\in L\}$

I am interested in proving that if $\sqrt{L}=\{w:ww\in L\}$ is regular if $L$ is regular but I don't seem to be getting anywhere. If possible I was hoping for a hint to get me going in the right ...
2
votes
1answer
83 views

show that language $L'$ is regular (given $L$ regular)

I am working on the following question: $L$ is regular. Show that $L'=\{x|\exists y,z,\ xyz\in L\wedge |x|=|y|=|z|\} $ is also regular. Firstly I show my idea. When you accept it I will try to ...
1
vote
0answers
54 views

How to draw a clearly arranged DFA of a language with modulo rules?

I know how to draw a DFA, but I have problems with this specific one: ${L = \{ w \in \{a,b,c\}^* \mid \ |w|_a \equiv |w|_b - 2|w|_c \mod \ 5 \} }$ This language is regular and there has to exist a ...
0
votes
0answers
27 views

$L = \{a^{n^3} | \ge 0\}$ Use the Pumping Lemma to show that L is not regular [duplicate]

Use the Pumping Lemma to show that $L$ is not regular: $$ L = \{{a^{n^3} | \ge 0}\}$$ I feel like I have a good intuition of what the Pumping Lemma states; strings that belong to a regular language ...
-1
votes
2answers
44 views

Infinite sequence of regular languages over fixed finite alphabet

Construct an infinite sequence of regular languages $L_1, L_2 , \ldots$, over the same fixed finite alphabet, such that for every $i ≥ 1$, $L_i ⊇ L_{i+1}$ and $|L_i \setminus L_{i+1} | = ∞$.
-2
votes
2answers
53 views

I think I have a regular expression for a non-regular language

Let $W = \{a^n b^m \mid n\ge m+5,m\le 5\}$, where $\Sigma=\{a, b\}$. I have proved that this language is irregular through pumping Lemma. But through regular expression it is proving that the ...
4
votes
1answer
109 views

Right equivalent elements arising in the proof of the Schützenberger Theorem

As a part of my Bachelor thesis in computer science I should review the proof of the Schützenberger Theorem (which was given by M.P. Schützenberger himself $^{[1]}$). My question arises on page 193 in ...
0
votes
1answer
41 views

Showing that $\{ c^n a^m b^{n+m} : n+m \geq 6\}$ is not regular [duplicate]

I'm trying to show that $L_6=\{c^n a^m b^p : n+m=p,p \geq 6\}$ is not regular. I need a little help, I was practicing the pumping lemma, and I encountered this language, I saw these conditions and got ...
0
votes
2answers
67 views

How to prove that these two languages are regular, or not regular? [duplicate]

I have these two languages $L_1={\{a^n b^m,n≥m+5,m>0}\}$ Where $∑=(a,b)$ $L_2={\{a^n b^m,n≥m+5,m≤5}\}$ Where $∑=(a,b)$ As you can see that there is only one difference, the condition of ...
1
vote
1answer
56 views

Proving that any CF language over a 1 letter alphabet is regular

I would like to prove that any context free language over a 1 letter alphabet is regular. I understand there is Parikh's theorem but I want to prove this using the work I have done so far: Let L be a ...
2
votes
2answers
42 views

How can I see which language type will result from the union or intersection of different language types?

I have to decide which language type will result from the union of a type-2 (context-free) and a type-3 (regular) language. Is there a way or rule to decide this for all language types?
4
votes
1answer
106 views

Possessive Kleene star operator

Has anyone studied the consequences of the Kleene star in regular expressions to always be "possessive"? In other words, if * would always match as much as ...
3
votes
1answer
109 views

Why is $\{a^n b^m c^p: n\neq m\} \cup \{a^n b^m c^p: m\neq p\}$ an inherently ambiguous language?

I came across a very hard interview question in last month’s Ph.D. entrance exam. It was asking which one of the languages is inherently ambiguous. Short answer says 2). Why is the language in 2) an ...
-3
votes
1answer
68 views

Prove A² is regular [duplicate]

Suppose that $A$ is a regular language. How can I show that $A^2 = A \cdot A$ is a regular language? Is there a construction?
-1
votes
1answer
32 views

Kleene star property: proving $(A^+)^* = A^*$ [duplicate]

I should prove that $(A^+)^* = A^*$ in a very formal way, any hints?