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

learn more… | top users | synonyms

2
votes
1answer
17 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
26 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
29 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
votes
0answers
10 views

Pumping lema solution [duplicate]

In a CS course we have an example {a^2^n | n >= 0} is this language regular or not? Is there anyone who can make pumping lemma contradiction ? Thank you for your answer
-4
votes
0answers
25 views

Are $\{a^n \mid n \geq 0\}$ and $\{a^p \mid p \text{ is a prime number}\}$ regular? [duplicate]

In a CS course I have the languages $\{a^n \mid n \geq 0\}$ and $\{a^p \mid p \text{ is a prime number}\}$. Are those languages regular or not ? Is there anyone who can make a pumping lemma ...
1
vote
2answers
66 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
13 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
27 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
66 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 ...
-1
votes
0answers
22 views

$L$ is regular. Show that $L_{+--}$ is regular

$L$ is regular, show that $$L_{+--}=\{w \mid \exists_{u} |u|=2|w| \wedge wu\in L\}$$ is also regular. I have a problem with this task, I tried construct automata from language $L$ but I can't see it. ...
2
votes
1answer
48 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
44 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
26 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
37 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
45 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 ...
3
votes
0answers
94 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
34 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
60 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
44 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
41 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
101 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
98 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
63 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
30 views

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

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

regular expression of star-height 1

Is there a regular expression of star-height 1 (i.e. without two nested Kleene stars) for the following language : $a^*(bb^*aa^*ba^*)^*$ ?
1
vote
0answers
23 views

Number of states of finite automata [duplicate]

Prove that for each $n>0$, a language $L_n$ exists where $L_n$ is recognizable by an NFA that has $n$ states, and If $L_n=K_1 \cup \dots \cup K_k$, for regular languages $K_i$, then at least ...
0
votes
0answers
12 views

Show that the language is regular [duplicate]

Let $L=\{k |km \in K \text{ for some } m \in M\}$. How can we show that if $K$ is regular and $M$ is any language, then $L$ is regular??
1
vote
2answers
60 views

Are regular languages closed against an intersection that keeps words with the same number of ones?

How can we show that the class of regular languages is closed under the following operation? Let $L_1$ and $L_2$ be laguages over $\Sigma=\{0, 1\}$. The operation is: $$\{x \in L_1 \mid \text{ for ...
2
votes
0answers
89 views

DFA for a regular language

I have a regular language consisting of such {0,1}^k sequences, in which every subsequence of length 5 has at least two 0's in ...
0
votes
2answers
77 views

Intersection of a language with a regular language imply context free

Lets say you have a language $L$ and you want to determine if it is context free. Context free languages intersected with regular languages are context free. Is that enough to prove that $L$ is ...
0
votes
1answer
47 views

designing a DFA and the reverse of it

There is a theorem that says if a language is regular, it's reverse is regular as well. How can I draw a DFA that shows if a language is regular, it's regular as well?
0
votes
1answer
38 views

What kind of subset any class of languages may or may not have?

There are different class of languages, regular,CFL, recursive and r.e. and non-r.e. Clearly a language is set of strings. if an infinite set belongs to any of these classes then what can we say about ...
1
vote
1answer
69 views

Is this language regular or non-regular: {ww : w ∈ {a,b}* } [duplicate]

This is a question from a text book that's giving me some trouble. The question is: Determine whether or not this language is regular. Justify your answer. $$L = \{ww : w \in \{a,b\}^* \}$$ I ...
0
votes
1answer
40 views

How do you prove two languages are equivalent using the definition of acceptance?

I need to prove that $L(f(M)) = L(M)\cup \{\varepsilon\}$ where $M$ is a DFA and $f$ is the function $f(M) := (Q\cup \{q_f\}, \Sigma, \delta', q_f, F\cup\{q_f\})$ and $q_f$ is a new state not in $Q$ ...
3
votes
1answer
150 views

How does a regular language satisfies the second condition of the pumping lemma

I'm a little bit confused about the second condition of the pumping lemma which are: $|y|\geq1$ $|xy|\leq p$ $\forall i \geq 0:xyiz\in L$ I don't understand why the length of ...
1
vote
1answer
34 views

Generate Regular Grammar for a Language with Modular Condition

This is a homework problem. I've wrestled with it for quite awhile and can't come up with a valid solution. The problem is: Find a regular grammar that generates each of the following languages: ...
0
votes
1answer
78 views

If L1 ∪ L2 and L1 are regular, is L2 also regular?

This is a problem in a theory of computation book that's stumping me: Suppose that we know that $L_1 ∪ L_2$ and $L_1$ are regular. Can we conclude that $L_2$ is regular? Explain. At first, I ...
1
vote
2answers
27 views

Prove that a language is not regular with process of elimination [duplicate]

When deterministic automaton, I need to prove that you can't implement the language in it, because the language is not regular. Easiest way to prove that a language is regular, is just by making an ...
0
votes
0answers
24 views

How these languages are context free and regular [duplicate]

I found these statements in my textbook without proof. If L is a Context Free Language over a one symbol alphabet then L is regular. Is there no context free language on one symbol ...
0
votes
1answer
52 views

Pumping Lemma confusion

I have the following language... $$A=\{a^ib^i | i>0\}\cup\{a^jb^k|j>2, k>3\}$$ Now, pumping lemma states that a regular language can be written in the form $x=pq^ir$. What confuses me is ...
2
votes
1answer
78 views

An example of a non-regular grammar for a regular language?

I understand that a regular language can be specified by either regular or non-regular grammars. What is an example of a non-regular grammar for a regular language?
0
votes
1answer
45 views

Pumping Lemma for Regular Language seems to Fail

Let $L = \{ab^ncd \mid n \geq 0\}$. If we take $p = 5$ and $w = abbcd$ and write $w_i = xy^iz$, where $x = abb$, $y=c$, $z=d$, then $w_2 = abbccd$ which is not in $L$. We conclude that ...
1
vote
1answer
35 views

Closure properties between 2 languages of different types [duplicate]

Whenever said - The intersection between a Context Free Language and a Regular Language is always Context Free, what is the best logical way to confirm the statement? I have this Chomsky hierarchy in ...
1
vote
1answer
86 views

Relaxation of the null production restriction in Regular and Context Free Grammars

I am convinced of the fact that allowing productions of the form $S \rightarrow \epsilon$ in a context sensitive grammar would allow RE languages to be expressed if $S$ were on the right hand side of ...
0
votes
0answers
25 views

What is the procedure for converting this finite automaton into a regular expression? [duplicate]

Could someone provide an explanation of how to convert this DFA into a regular expression? I have found three methods online, ie: How to convert finite automata to regular expressions? but they are ...
0
votes
1answer
97 views

What is meant by the notation $L(…)$?

I am currently studying about formal languages and automata. I am trying to solve a problem but there is a notation whose meaning I'm not sure of. I have a question to find out the relationship ...
0
votes
1answer
93 views

How do I show that $a^n w b^n$ is not regular?

Given $ \Sigma= \{a,b\} $, show that $ L:= \{a^nwb^n: m,n \in \mathbb N, m\geqslant n, w\in\Sigma^m\} $ is not regular. I'm trying to proof this with the Pumping Lemma, but I'm kind of confused ...
0
votes
1answer
65 views

closure property on languages

The above image, taken from planetmath.org, describes the closure property on REG (regular), DCFL (deterministic context-free), CFL (context-free), CSL (context-sensitive), RC (recursive), RE ...
1
vote
1answer
56 views

Understanding Regular Grammers

I know a regular language is the one which can be expressed as a regular expression or we can create a DFA corresponding to it. Unless a language has a pattern in which one part has to match with ...
0
votes
1answer
58 views

Union of finite and non-regular language [duplicate]

Question: ($B$ and $C$ are languages) $B$ is finite,$C$ isn't regular: Prove/Disprove: $C\cup B$ isn't regular. Thoughts: My intuition says this is true, but I need an idea to prove it. Since I ...