Questions tagged [regular-languages]
Questions about properties of the class of regular languages and individual languages.
1,462
questions
-1
votes
2answers
40 views
how to solve this question
Let Ξ£ be some alphabet. We define the following operation on the set of all languages
over Ξ£. The operation 3MAJ(L1, L2, L3) takes in three languages L1, L2 and L3 and
outputs the language of all ...
1
vote
1answer
30 views
Constructing a NFA that accept complement of language L of another NFA
if given a language $L$ recognized by NFA $N_0$ over an alphabet $\Sigma$. Is it possible to find a general way of constructing an NFA $N_1$ that accept $L^C$ such that $L^C= \{w \in \Sigma^{*} |\mid ...
0
votes
2answers
41 views
Show $\{0^𝑚1^𝑛|𝑚β 𝑛\}$ is not regular
So I have the question: show "Show $\{0^π1^π|πβ π\}$ is not regular". I've already seen various proofs for this question, but they all have one step I don't get.
They all take: $\bar{L}β©(...
1
vote
0answers
14 views
Language of all words of the form $xwwy$, where $x,w,y \neq \emptyset$ [duplicate]
I have the following question:
Determine whether the following language is regular or not, and prove it:
$$L = \{xwwy \mid w,x,y β Ξ£^*,w,x,y \neq Ξ΅\}. $$
My idea was that any string with at least 1 ...
0
votes
0answers
18 views
If L is a regular language, then the particular Lβ² is also regular? [duplicate]
Show that if $L β Ξ£^β$ is a regular language then the following language is also regular:
$$L' = \{w\mid βx, y β Ξ£^β : w = xy β§ yx β L\}$$
Can you give me a hint how to solve that?
-1
votes
0answers
13 views
LL(1) Eliminate Ambiguous Ξ΅-derivations
I have this grammar I want to convert to LL(1):
S -> A B a | A B b
A -> A c | B d
B -> A a | b
I eliminated the left-recursions, I factored out the ...
1
vote
1answer
20 views
How does a transition function behave in a FSM when an input is not recognized (i.e. the input is not contained in the alphabet)?
In Sipser's Introduction to the Theory of Computation, the provided proof for the union operation being closed for regular languages has a step for the transition function that I find a bit lacking.
...
1
vote
1answer
29 views
Difference between $ L_1 = \{(a^n b^n)^m \mid n, m \ge 1\} $ and $ L_2 = \{a^n b^n \mid n \ge 1\}^+ $
Is there any difference between saying
$ L_1 = \{(a^n b^n)^m \mid n, m \ge 1\} $
with $ L_2 = \{a^n b^n \mid n \ge 1\}^+ $?
I know that for $v = abab$ we have $v \in L_1$ and $v \in L_2$
my ...
1
vote
1answer
48 views
Why does the Pumping Lemma Constraint |xy| β€ p mean that y can't be 1 in the string 0p1p
I am trying to get my head around the Pumping Lemma to prove a language is non-regular.
I am reading the Sipser text book and he gives the following example.
Let B be the language $\{0^n 1^n | n \ge 0\...
-1
votes
2answers
51 views
DFA for $\{0^m1^n \mid m+n \text{ is even}\}$
How do I construct a DFA for the language $\{0^m1^n \mid m+n \text{ is even}\}$? The corresponding regular expression is
$(00)^*(11)^* + (00)^*0(11)^*1$.
1
vote
1answer
49 views
How to prove a language isn't necessarily regular? [duplicate]
Assuming we have a regular language $L$, how can we prove that $L'= \{ xz \mid \exists y : xyz \in L \text{ and } |x|=|y|=|z|\}$ isn't necessarily regular.
So far I can't come up with much for how to ...
1
vote
1answer
36 views
All prefixes with same length as their suffix is a regular language
Suppose $L$ is a regular language over $\Sigma$ and we want to show that $$\frac{1}{2}L = \{x \in \Sigma^* \mid \exists y \in \Sigma^* (xy\in L \wedge |x| = |y|)\}$$ is regular. I thought of taking ...
3
votes
1answer
101 views
Why do we need Kleene Star when there is concatenation?
For an alphabet $A = \{ a_1, a_2..., a_n \}$, the set of regular langages $L_r$ on $A$ are recursively defined by closed union, concatenation, and Kleene star's operator. I understood that languages ($...
1
vote
1answer
23 views
Using closure properties, prove that $L=\{a^kb^ra^m|k,r,m\ge0 \text{ and } m=k+r\}$ is not regular
I'm trying to prove that $L=\{a^kb^ra^m|k,r,m\ge0 \text{ and } m=k+r\}$ is not regular and, although it's trivial to prove it via pumping lemma, I'm having troubles trying to find a way to prove it ...
1
vote
1answer
47 views
Computing $(a+b)^*c^*(a+b)^* \cap (b+c)^*a^*(b+c)^*$
how can I find the regular expression for this intersection ?
I've tried to find words but it did not help too much..
$$[\; (a+b)^* c^* (a+b)^* \;] \cap [\; (c+b)^* a^* (c+b)^*\;]$$
1
vote
1answer
28 views
Intuition for irregular languages
I'm struggling in understanding how to recognize irregular languages.
I know what the meaning of irregular language but still find it hard to recognize.
Are there any tips to recognize better and to ...
1
vote
1answer
25 views
All strings in which every substring 000 appears after every 1
I found this given problem as follows:
Write a regular expression where all strings in which every substring 000 appears after every 1.
Now, I also found the answer from Illinois university study ...
2
votes
1answer
52 views
Formal Binary String Regular Expression (each pair of 00 must have 11 before it)
I'm trying to construct a regular expression for the language of binary strings in which every 00 must have at least two 1s before it.
I realize this can be done with lookbehinds using the following ...
2
votes
0answers
31 views
Subexponential size of string to prove $\{xy : x,y \in \{0,1\}^\star, |x| = |y|, x \ne y\}$ is not regular?
In the standard proof of this language not being regular using the Pumping Lemma for Regular languages, one picks $0^p 1^p 0^{p+p!} 1^p$ where $p$ is the pumping constant and using that can derive the ...
1
vote
1answer
57 views
Can you reduce every decidable language to a regular language?
One of my previous questions on an exam was the following
Can you reduce a decidable language to a given regular language? (decidable language $\leq _m$ regular language).
If so, does this mean that ...
1
vote
1answer
29 views
Finite languages $L\in RE$
I want to check if I understood it in the right way.
In some example where $L\in RE$ the explanation deal with 2 cases: 1st when $L$ finite and 2nd when $L$ infinite. In the second case $L\in R$, isn'...
0
votes
1answer
59 views
Proving that a certain language is regular using pumping lemma
Let $\Sigma = \{a,b,c,\ldots,x,y,z\}$ be the Latin alphabet, consisting of 26 letters. Consider the language $L$ of all words $\alpha$ over $\Sigma$ satisfying the following constraints:
If $\alpha$ ...
2
votes
1answer
28 views
Unique decipherability of infinite regular language
Can we design an algorithm to test if a infinite regular language is a code?
We have the S-P algorithm to determinate if a finite language is a code. But how about the infinite part of regular ...
0
votes
0answers
16 views
Check if the regular expression r made up of the single symbol alphabet Ξ£ = {a} defines language L(r) = a* [duplicate]
I have got to write an algorithm programatically using haskell. The program takes a regular expression $r$ made up of the unary alphabet $ \Sigma = \{ a \} $ and check if the regular expression $r$ ...
1
vote
1answer
38 views
Regular Languages and Separating Suffixes
Preparing for the next semester, I wanted to give the following as a homework question, yet after a few attempts, I failed to solve it.
Given a language $L\subseteq \Sigma^*$ and two words $x,y\in \...
3
votes
2answers
90 views
Is $L:=\{a^k \mid k \text{ is prime}\}$ regular?
For this exercise the pumping lemma should be used. My instructor gave me a tip it should start with $w:= a^{prime(n)}$ where prime is a while program returning the nth prime number. This does make ...
1
vote
3answers
54 views
Regular Expression for language [duplicate]
I have a grammer with the following productions,
S -> aA | bC | b
A -> aS | bB
B -> aC | bA | a
C -> aB | bS
I have to construct regular expression for ...
0
votes
1answer
27 views
Some questions regarding decidability and semi-decidability of $A/B = \{ w \text{ | }\exists z \in B, wz \in A\}$
I have found two interesting questions regarding the quotient of languages, described as:
$A/B = \{ w \text{ | }\exists z \in B, wz \in A\}$
The first one is:
Let $A$ and $B$ be regular languages, ...
1
vote
3answers
234 views
Pumping lemma: why x in β£xyβ£ β€ p?
Looking at the pumping lemma, I've noticed that in the string $xy^pz$, there seems to be no rule explicitly stated for $x$ and $z$. If I understand correctly, $x$ and $z$ are basically anything on the ...
0
votes
0answers
15 views
Regular expression for all words not containing 222 [duplicate]
I need to find a regular expression for the language of all words over $\{0,1,2,3\}$ which do not contain $222$ as a substring.
2
votes
1answer
68 views
Which closure properties are always valid between regular, context-free and non context-free languages?
I am making a scheme that respresents some closure properties (union, intersection, complement and concatenation) for regular languages, context-free languages, decidable languages and RE languages. ...
0
votes
2answers
89 views
Find language and regular expression
I don't know how to find the Language and the regular expression for each one.
there are any special method for those kind of question?
1
vote
1answer
44 views
Using the pumping lemma for a specific language
Please help me with the following question:
Define the language LONGERB to be the set of strings over $\{a,b\}$ where the longest substring containing only $b$βs is strictly longer than the longest ...
0
votes
1answer
36 views
If L is context free and R is regular then R β L must be context free?
Hi I am wondering if L is a CFL and R is RL then would the difference R - L be a context free language?
The difference might be the CF part of the language left then it would be, but I'm not sure how ...
1
vote
1answer
28 views
What is the language of Sigma^n? Confused about meanining
I am learning the Theory of Computation, and I came across the language $\Sigma^n$. Could someone please explain what that could mean if $\Sigma$ is the alphabet?
Thank you so much!
1
vote
1answer
31 views
Finding right quotient of $a^*b^*/b^*.$
I argue that right quotient of $a^*b^*/b^*$ is $a^*$,is that true?any help or argument to accept or reject my argument will be appreciated:)
2
votes
1answer
55 views
Minimal DFA accepting strings whose length is divisible by $x$ or $y$
Consider the language of all strings whose length is divisible by either $x$ or $y$, where $x,y \geq 1$.
After trying various values of $x$ and $y$, I noticed made the following observation:
If one ...
-1
votes
2answers
60 views
Difference between a regular and a non-regular language
Suppose $L_1$ is a regular language and $L_2$ a non-regular one, then:
is $L_1\setminus L_2$ REGULAR/NON REGULAR/BOTH OF THEM?
is $L_2\setminus L_1$ REGULAR/NON REGULAR/BOTH OF THEM?
1
vote
0answers
33 views
Over every non-empty alphabet there exist languages which are non-regular
I am not sure about the answer. Intuitivly I would say that there are alphabets for which there are no non-regular languages. In particular I am thinking of languages with only one element. But I am ...
0
votes
0answers
22 views
State machine to convert from base 2 to base 10?
Is there a state machine which can convert base 2 decimals to base 10 decimals in a streaming fashion? Integers?
2
votes
1answer
46 views
Construct a CFG for $L = \{ w \in \{0,1\}^*\text{ } |\text{ } w = w^R \text{ and } |w| \text{ is even}\}$
I need to construct a CFG for the following language$$L = \{ w \in \{0,1\}^*\text{ } |\text{ } w = w^R \text{ and } |w| \text{ is even}\}$$
I know that the two middle position should always be the ...
0
votes
1answer
34 views
Can someone please help with the proof of this?
Given an unambiguous context-free language L and an unambiguous regular language L (moreover, every regular language is unambiguous) such that Lβ© R = β
, then prove that Lβͺ R is also unambiguous.
0
votes
1answer
31 views
Create an Finite Deterministic Automata for a regular expression
I want to create a finite state machine that accepts the following language:
$$
L=\{w\in\{a,b\}^* | w \text{ contains abb but not on the first position}\}
$$
So I began by writing a regular expression ...
1
vote
2answers
67 views
Proving some subsets of a regular languages to be regular languages
I have to prove that if a language $L$ is regular then:
a) $NONPREFIX(L)=\{u \in L / $none of the prefixes (not $\epsilon$ or $u$) of $u$ are elements of $L \} $ is regular
On this one I think I can ...
0
votes
1answer
27 views
How do i prove this language is regular? [duplicate]
I have this language {0+1+0+} and i need to prove it is regular,i had the idea to use the closure properties but i can find any regular languages to unify perhaps.Any ideas?
2
votes
1answer
68 views
How can I show that this language is context sensitive?
I have this language $L=\{a^nb^nc^n,n\geq0\}$, I know this language is not context free, but I don't know how to show that it is context sensitive, do I have to use a PDA?
1
vote
1answer
44 views
Is this language based on the number of $a$'s of a word over alphabet ${a, b}$ context-free?
I'm trying to use the pumping lemma, to show that the language $L = {w \in \{a, b\}^+: na(w) = nb(w)}$ is not context free, where $na(w)$ is the number of $a$'s in $w$.
I have this: By contradiction, ...
0
votes
1answer
37 views
How to check if a language is not regular?
I have the given regular language and i am suppose to check if it is regular and if it is, to provide a regular expression
However, if the language is not regular i have to prove using the "...
0
votes
1answer
19 views
Relationship between Kleene Star of a subset of regular language and the regular language
If $L(R_1) \subseteq L(R_2) \subseteq L(R_3)$ then $L(R_1)^* \subseteq L(R_2)^* \subseteq L(R_3)^*$. Does this also imply that $L(R_1)^* \subseteq L(R_3)$?
2
votes
1answer
62 views
What are the most used statements in programming (ranked)?
I was wondering if there are any resources for a study/ranking of the most frequently used statements (by statements I mean assigning, invoking, instantiating etc, like in C#) in programming overall (...
