Questions tagged [regular-languages]

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

Filter by
Sorted by
Tagged with
-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 (...

1
2 3 4 5
30