Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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

1
vote
1answer
32 views

Find equivalence classes of language $L = \{0^n1^n, n \in \mathrm{N}_0 \}$

I'm asked to find all equivalence classes of the language $$L = \{0^n1^n, n \in \mathrm{N}_0 \}$$ We have the following definition: $$(xR_Ly)\Leftrightarrow (\forall w\in \Sigma^* xw\in L \...
2
votes
1answer
61 views

Regularity of language of words containing a square

$$L = \{w\mid w\text{ contains a substring of form }yy\text{, where }y\text{ is any non-empty string}\}.$$ Is this language regular? We do not know what $y$ looks like in advance. And why is this ...
0
votes
1answer
42 views

Why does removing all copies of a letter preserve regularity?

Let $P(a,L)$ remove every $a$ in $L$, for example $$ P(a,\{ab,aab,aaab,bba\}) = \{b,bb\}. $$ How to show that if $L$ is a regular language then $P(a, L)$ is also a regular language? My attempt: If $...
0
votes
2answers
26 views

How to deal with character set in regular expression?

In regular expression implemented by language like perl or python, user can write a set of characters like [123abcd] or special notation like \d to represents digit ...
0
votes
0answers
16 views

Is the set obtained by taking the first quarter of strings from a regular set $L$ regular as well? [duplicate]

That is, let $L'$ be the set consisting of the first quarter (first $\frac{1}{4}^{th})$ of each string whose length is divisible by 4 in a regular set L. I am pretty sure $L'$ is regular, but I am not ...
1
vote
1answer
28 views

Is my pumping lemma proof correct? [duplicate]

Show that $L = \{a^nb^l \ | \ n \leq l \}$ is not regular I'd like to check if my proof for this is correct. Proof: Choose any positive integer $m$. Pick $w = a^mb^{m+1} \in L$. Note that $|w| = 2m+...
6
votes
3answers
2k views

Prove that A** = A*, where A is a language over Σ*

Let $\mathcal A$ be an arbitrary language over $\Sigma^*$ Proof. To prove, $\mathcal A^{**} = \mathcal A^* $ $\mathcal A^{**} = \left( \mathcal A^0 \cup \mathcal A^1 \cup {...} \cup \mathcal A^n \...
0
votes
2answers
119 views

Non-regular language whose prefix language is regular

I understand that prefix of a regular language is regular, but I am unable to get my head around this: Give an example of a non-regular language $A ⊆ \{0, 1\}^*$ for which $\operatorname{Prefix}(A)$...
0
votes
1answer
39 views

What is an infinite language?

I just started reading about formal language theory and what i have learnt so far that: Alphabet is a finite set of symbols. String/Word: is always finite. Because a language is set of strings of ...
1
vote
1answer
43 views

If $L$ is a regular language, then $s(L)$ is also regular

...where $s$ is a substitution that replaces each symbol of each string in $L$ with a regular expression. For example, if $L=a^*b$ and $s(a) =ab, s(b) = b^*$, we have $s(L) = (ab)^*b^*$. My ...
0
votes
2answers
115 views

How does modulus affect the regularity of language?

the question is as follows, further the notation used are standard as used in theory of computation $$L = \big\{ w : w \in \{a,b\}^*,\ |n(a) - n(b)| = 2k\}\,.$$ Beware 'K' is not a fixed integer its ...
0
votes
0answers
23 views

How to come up with regular expression or FSA for such language? [duplicate]

L=$\{aba^R \mid a,b \space \epsilon \space \{0,1\}^* \space \}$ I need to prove this language is regular. I know that we need to come up with a regular expression or DFA/NFA but could not think of a ...
0
votes
3answers
626 views

is this language regular and why pumping lemma doesn't work?

I was told that this language is regular but as I can show below, pumping lemma is not working for it. What am I doing wrong? Is this language really regular? Why?
0
votes
1answer
68 views

Trying to simplify a particular regular expression

The question is as follows $$(a^* (ba)^* )^* (b+\epsilon) = (a+b)^* (b+\epsilon)\,.$$ But I am unable to solve this regex expression. My answer is as follows: \begin{alignat*}{2} (a^* + (ba)^* )^...
0
votes
2answers
62 views

Does there exists a finite automata for the given language?

The question is simple and given as, $alphabets=\{a, b\}$, and language $L$ over them as: $L = \{w: w \ € \{a, b\}^*, (n(a) - n(b)) \ mod \ 3=1\}$. Here $n(a)$ = number of $a$ and $n(b)$ is number of ...
1
vote
1answer
18 views

Proving irregularity of $\{a^nb^k \mid n > k \text{ or } n \neq k-1\}$

I need help with proving the following language is not regular: $$ L = \{ a^n b^k \mid n > k \} \cup \{ a^n b^k \mid n \neq k-1 \} $$ My usual methods using pumping lemma are not getting me ...
2
votes
1answer
64 views

Closure of regular languages under deleting a 1 from each even run of 1s

Let $R$ be a regular set over the alphabet $\{0, 1\}$. Give a machine construction to prove that the set obtained by deleting one 1 from each even length block of 1’s is also regular, and using ...
0
votes
0answers
30 views

regular language for NFA [duplicate]

I'm trying to find the w-regular language of this NBA. In 'Principle of Model Checking' - Book there's an algorithm for this problem: 1. Take the NBA as NFA and create the regular language to get from ...
0
votes
0answers
48 views

Regular expressions - Do i need the $*$ inside $()^*$-brackets?

Do i need the $*$ after the first $B$ in this regular expression $(B^* + C)^*$ ? Do i need the $+$ after the first $B$ in this $\omega$-regular expression $(B^+ + C)^\omega$ Stated differently: Is $(...
1
vote
1answer
59 views

Can we prove using pumping lemma that language F = {$a^ i b ^j c ^k$ | i, j, k ≥ 0 and if i = 1 then j = k} is not regular?

I am currently solving a problem in which we have to show that we can not prove using pumping lemma that the language mentioned in the question is not regular.Here is the full question Consider the ...
3
votes
1answer
30 views

Given the regular set $S = a^*ba^*ba^*$, is the set $S'$ of all first thirds of strings in S (with length divisible by 3) regular?

I have no idea how to approach this problem, could I get at least a hint on how to go about proving/disproving this? I've tried the pumping lemma but I don't think it applies here. I've also tried ...
4
votes
1answer
50 views

Efficiently convert an NFA with multiple $\varepsilon$ edges and accepting states into a regular expression

Given an NFA with alphabet $\Sigma = \{a, b, c\}$ defined in the diagram, is there a way to efficiently convert it into a regular expression? The way I solved this problem is to first convert the NFA ...
6
votes
2answers
294 views

Find the language an NFA recognizes

For example, I have an NFA $A_n$ with alphabet $\Sigma = \{0, 1\}$. The language recognized by this NFA is known to be $\{u1v\ |\ u, v \in \Sigma^*, |v| = n − 1\}$. I was unable to get the ...
2
votes
2answers
81 views

Finding if the given language is regular or not

I have the language $$L = \{a^mb^nc^o| \, m + n + o > 5\}$$ where $m,n,o$ are non-negative integers. I have to find whether the language is regular or not. My attempt: I feel it should be non ...
0
votes
0answers
57 views

Proof: class of regular language is closed under union operation with different input alphabet

Tha class of regular lanugage is closed under the union operation. If $A_1$ and $A_2$ are regular languages, then so is $A_1 \cup A_2$. Thus, there are two finite automatons(FAs) $M_1$ and $M_2$ ...
0
votes
1answer
16 views

Choose the best classifier to predict the label of strings of a regular language

I have to tackle this problem: I have some strings that are my training set. These strings belong to a regular language corresponding to a deterministic finite automata (hidden namely I don't now it, ...
2
votes
1answer
26 views

Regular expression for capturing a “C-style” string

I have started to learn automata theory and languages. I am new to regular expressions. As a use case in real world, I would like to construct a regular expression to accept a c-style string: ...
1
vote
2answers
73 views

Is every regular/context free langauge decidable in LogSpace?

I know all the regular languages are decidable but not sure whether it can be done in LogSpace.
0
votes
1answer
44 views

Is the language $K=\{u \in\{0,1\}| n \geq 0, \forall_{v \in\{0,1\}^n} (u+v) \in L \}$ regular?

For two words $w,v \in\{0,1\}^*$ of equal lenght, let $w+v \in\{0,1,2\}^*$ denote the word in which the $i$-th word is the sum of $i$-th position of $w$ and $v$, as follows: if $w=a_1 \ldots a_n$ and $...
-1
votes
1answer
37 views

How to convert a CFL to a deterministic PDA?

I am trying to complete this question. However, I am unsure of the steps necessary to complete the conversion from a CFL to a deterministic PDA. I know that $ww' | w \in \left \{ a,b \right \}^{*}, w'...
3
votes
2answers
33 views

Question about mapping reducibility

I am working on an assignment where one of the sub questions is: Let $A$ and $B$ be languages. Suppose $A$ is context free and $A ≤_m B$, which means that there is a computable function $f\colon \...
2
votes
2answers
129 views

Is DFA and Regular Expression equivalent?

The language of a DFA can be the empty set (by defining no final states), but can a Regular Expression do that? If Regular Expression cannot do that, does it mean that DFA and Regular Expression are ...
6
votes
3answers
1k views

How to prove using pumping lemma that language generated by a(b*)c(d*)e is regular?

I am studying pumping lemma from Introduction to theory of computation by Michael Sipser. I wanted to check if the language generated by regular expression ...
1
vote
1answer
26 views

Minimum number of letters

I have an assignment that I have to do and the question is Draw a DPDA that accepts the language L = {ba(bb)^(n+1)a^(n – 1) |n > 1}. Im not looking for the answer but rather some direction. I ...
4
votes
1answer
57 views

Is the symmetric difference of a non regular language L and a finite language f non regular?

The symmetric difference of $L_1$ and $L_2$ is defined to be: $(L_1-L_2) \cup (L_2-L_1)$. Problem: I’m trying to prove that given L a non regular language and F a finite language there symmetric ...
1
vote
1answer
48 views

Proof that (A ∪ B)∘C = A∘C ∪ B∘C where A, B and C are languages

How can I prove this identity of languages? My aproach is the following: Let A, B and C to be languages, and let x to be an arbitrary string. (A ∪ B) ⇒ x ∈ A ∨ x ∈ B How do you proceed?
0
votes
1answer
47 views

Define a grammar to emmulate chess rules

Is it possible to define a 《chess language》: language={alphabet = {(chess pieces, squares of chess board)}, grammar={rules of movement of pieces over the board}}? I looked online but I cannot find a ...
-1
votes
1answer
42 views

Prove {0^n OR 1^2n OR 2^3n | n >= 0} is not context free

How to prove using pumping lemma {0^n OR 1^2n OR 2^3n | n >= 0} is not context free This isnt the same language as {0^n1^2n2^3n | n >= 0} as this language the numbers need to be in order.
1
vote
1answer
30 views

Contradiction in regularity of a language

Lets say we have $L_1$ which contains all binary numbers divisivle by 2 but not by 4. I would say this language contains all words with a 10 at the end. Ive found a regular grammar $G$ with $L(G) = ...
-2
votes
2answers
88 views

Context free Grammar for this context free language

How can I create a context free grammar for the language $\{p^2q^mpr^nq^{2n+m}| m,n \ge 0\}$, where $\Sigma = \{p,q,r\}$?
2
votes
1answer
255 views

Determining if given languages are regular or recursively enumerable

I came across following problem: Suppose $L_1$ and $L_2$ are two languages, $M$ is a Turing machine $L_1 =\{M|M$ accepts at most 2016 strings$\}$ $L_2=\{M|M$ accepts at least 2016 strings$\}$ ...
2
votes
1answer
45 views

Is the language $a^nwa^n$ regular?

The given description of language is: $\Sigma=\{a,b\}$ and $L=\{a^nwa^n:n\geq 1,w\in\Sigma^*\}$ I felt its regular as we can always interpret $aabaa$ in string $aaabaaa$ as $w$. That is we can ...
0
votes
1answer
36 views

Generation regular languages by context free grammar

I came across problem asking whether given statement is true and false. The statement given was as follows: Every Type-2 grammar can generate regular language. I felt that Type-2 grammar means, ...
4
votes
2answers
77 views

Proving that $\{0^{m^2}\mid m\geq 3\}^*$ is regular

We know that $L=\{0^{m^2}\mid m\geq 3 \}$ is not a regular language. However $L^*$ is regular because we can generate $0^{120}$ to $0^{128}$ by some concatenations and then any other power of $0$ can ...
1
vote
1answer
29 views

Number of strings accepted by this regular expression

This was a question that I got while taking a test at our university. The question paper was taken away after the exams. I remember the question only, not the multiple choices. If a regular ...
0
votes
3answers
74 views

Concatenation of language to itself zero times

I was solving this question: Which of the following statement(s) is/are false? $L^0=\{\epsilon\}$ $|L^0|=0$ The answer given was None. That is, none of these statements are false and ...
1
vote
1answer
40 views

“Or” in regular expressions

I'm a bit new to automata theory, I'm sorry if this question is a bit too simple. If this question has been answered somewhere already, please point me to it. One basic problem I wanted to solve was ...
1
vote
1answer
108 views

Understanding facts about regular languages, finite sets and subsets of regular languages

I am aware of following two facts related to two concepts: regular languages and finite sets: Regular languages are not closed under subset and proper subset operations. It is decidable ...
1
vote
1answer
95 views

Difference between regular language and context free language

What is nature of difference of regular language and context free language? My guess is RL - CFL = RL CFL - RL = CFL Am I correct with this?
0
votes
0answers
33 views

Conversion from automaton to left linear grammar

I stumble across this problem: Give right linear grammar. The solution given was simple: $S\rightarrow bA$ $S\rightarrow aS$ $A\rightarrow \lambda$ $B\rightarrow bA$ $A\rightarrow aB$ Earlier ...