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 ...
