Questions tagged [regular-languages]

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

Filter by
Sorted by
Tagged with
2
votes
1answer
2k views

How come {ww} isn't regular when {uv | |u|=|v|} is?

As we know, using the pumping lemma, we can easily prove the language $L = \{ w w \mid w \in \{a,b\}^* \}$ is not a regular language. However, the language $L_1 = \{ w_1 w_2 \mid |w_1| = |w_2| \}$ is ...
2
votes
1answer
263 views

Regular vs LALR(1): what is faster

Supposing we have two grammars which define the same languge: regular one and LALR(1) one. Both regular and LALR(1) algorithms are O(n) where n is input length. Regexps are usually preferred for ...
1
vote
2answers
239 views

Is there a name/interest for regular languages that have a non-ambiguous ending?

The basic idea is to have one or more symbol that clearly indicate the end. For example: Non-ambiguous: $ab^*c$ $(a|b)c$ $ab^+c$ $ab?c$ $a(b|c)$ $c(ab)^*ccc$ $acc^*d$ $abc|bcd$ ...
0
votes
1answer
186 views

What is meant by "give pattern of a regular expression"

I have an alphabet $A = \{b,B\}$ and I'm asked to write down the pattern of the regular expression $(\epsilon|bb|b)(B|bb)(b|\epsilon|b)$. What does the question actually want me to do? I'm not sure. ...
4
votes
2answers
341 views

Is this language regular or not?

$L_1=\{a^ku \mid u \in \{a,b\}^* $ and $u$ contains at least $k$ a's, for $k\geq 1\}$. If it is regular, I haven't found its regular expression or any closure property to prove it. If not, it seems ...
2
votes
2answers
3k views

Pumping Lemma for regular language for $a^n$ where $n$ is even fails

$$L=\{a^n \mid \text{\(n\) is even}\}$$ This is regular but fails in the pumping Lemma. Assuming $m=4$, $w=aaaaaa$, $|w|=6$ (even). Let $w=xyz$, $x=a$, $y=aaa$. We have $|y|>0$ and $|xy| \le m$. ...
4
votes
1answer
5k views

Do self-loops in DFA cause infinite languages?

A true/false question: If a DFA $M$ contains a self-loop on some state $q$, then $M$ must accept an infinite language. The answer is "false". I've read this question, but I'm still wondering why $M$ ...
0
votes
1answer
251 views

Recusively Enumerable or Recursive dependent on whether P=NP

If a language is defined such that $L = (0+1)^{\ast}$ if $\mathsf{P} = \mathsf{NP}$ and $\emptyset$ otherwise Then $L$ is a regular language if $\mathsf{P} = \mathsf{NP}$, otherwise it is the ...
-1
votes
1answer
1k views

Formal Languages - Expressive power of Formalisms

I need help with the following question: Order the following formalisms according to their expressive power: placing A before B means that any language definable by A is definable by B. Also state ...
1
vote
1answer
226 views

Closure properties of languages

Let $P$ be a regular language and $Q$ be a context-free language such that $Q \subseteq P$(For example, let $P = a^*b^*$ and $Q = \{ a^nb^n | n \ge 0\}$). Then which of the following is always ...
1
vote
1answer
539 views

Is the intersection of two regular languages regular?

Trivially decidable problem is one in which the problem is a known property of the language/grammar. So intersection of two regular languages is regular should be trivially decidable? But it is given ...
2
votes
2answers
4k views

How can I prove that the language of a read-only Turing machines is regular?

I find this, but I can't complete it, is there any other solution for it?
26
votes
1answer
808 views

"Dense" regular expressions generate $\Sigma^*$?

Here's a conjecture for regular expressions: For regular expression $R$, let the length $|R|$ be the number of symbols in it, ignoring parentheses and operators. E.g. $|0 \cup 1| = |(0 \cup 1)^*| ...
3
votes
2answers
533 views

Proving regularity via equivalence classes

Given two regular languages $L_1$ and $L_2$, we define a new language $$L=\{w_1w_2\mid \text{ there exist two words } x,y \text{ such that } xw_1\in L_1, w_2y\in L2\}$$ How do I show that $L$ is ...
2
votes
2answers
686 views

Is this a regular grammar?

I went through a question asking me to categorize the following grammar. $$S → AA, S → AB, A → a, A→BB, B → b, B → e$$ From the production rules, clearly it is Context-Free. But it accepts a finite ...
2
votes
1answer
579 views

Does this DFA have a solution?

I am trying to create a DFA that can recognize strings with alphabet $\{a,b,c\}$ where $a$ and $c$ appear even number of times and where $b$ appears odd number of times. I am wondering that this may ...
6
votes
2answers
2k views

Space complexity below $\log\log$

Show that for $l(n) = \log \log n$, it holds that $\text{DSPACE}(o(l)) = \text{DSPACE}(O(1))$. It's well known fact in Space Complexity, but how to show it explicitly?
2
votes
2answers
200 views

Show that the language of strings not in the union of two regular languages is regular

Given languages $L_1,L_2$, defines $X(L_1,L_2)$ by $\qquad X(L_1,L_2) = \{w \mid w \not\in L_1 \cup L_2 \}$ If $L_1$ and $L_2$ are regular, how can we show that $X(L_1,L2)$ is also regular?
3
votes
1answer
334 views

Is this language regular?

Consider the following language: $$ L_1=\{uu^rv \mid u,v\in\{0,1\}^+\}.$$ that means that neither $u$ nor $v$ can be $\varepsilon$. As usual $u^r$ refers to $u$ reflected. I think that this language ...
8
votes
3answers
2k views

Proofs using the regular pumping lemma

I have two questions: I consider the following language $$L_1= \{ w\in \{0,1\}^* \mid \not \exists u\in \{0,1\}^* \colon w= uu^R\}.$$ In other words $w$ is not palindrome with even length. I proved ...
8
votes
3answers
747 views

Proving the language which consists of all strings in some language is the same length as some string in another language is regular

So I've been scratching my head over this problem for a couple of days now. Given some language $A$ and $B$ that is regular, show that the language $L$ which consists of all strings in $A$ whose ...
2
votes
1answer
216 views

Recursive and regular languages

I'm trying to study for an exam and having difficulty with the following practice questions. Any help would be appreciated. Give a language $L$ such that $L$ is not recursive but $\text{prefix}(L)$ ...
2
votes
2answers
2k views

Is $\{a^nb^m \mid n,m\ge 0, n\ne m\}$ regular or not? [duplicate]

Possible Duplicate: Prove that the complement of $\{0^n1^n \mid n \geq{} 0\}$ is not regular using closure properties Is $L=\{ a^nb^m \mid n,m \ge 0, n\ne m\}$ a regular language? I think it ...
1
vote
2answers
3k views

Language acceptance by DFA

I have some questions regarding acceptance of a language by DFA Whether more that one dfa accept a language Whether a dfa can accept more than one language
4
votes
2answers
304 views

Find non-regular $L$ such that $L \cup L^R$ is regular?

I've been studying for an exam I have tomorrow, and I was looking through some previous sample exam questions, when I came across this problem: Give a non-regular language $L$ such that $L \cup L^R$...
0
votes
0answers
55 views

Show that a language is not regular by Pumping Lemma [duplicate]

Possible Duplicate: How to prove that a language is not regular? Show that $L_2=\{a^nb^k|n\not= k-1\}$ is not regular by Pumping Lemma.
1
vote
1answer
196 views

How to prove $L \cdot L^{*} = L^{+}$

How can one formally prove $L \cdot L^{*} = L^{+}$ It looks obvious to me since with the concatenation you get rid of $\varepsilon$, but I cannot think of a formal proof through induction or ...
5
votes
1answer
2k views

Prove that the language of non-prime numbers written in unary is not regular

Im trying to prove that the following language is not regular. $$\text{Notprime} = \{a^n \text{where \(n\) isn't prime}\} = \{\epsilon, a, aaaa, aaaaaa, aaaaaaaa, \ldots\}$$ Heres what I have: "If ...
1
vote
1answer
3k views

How do you prove that two languages are equivalent?

How can you show that the Language accepted by an NFA and the reverse NFA is the same? For a language $L$, there is an $L^R=\{ w^R \mid w \in L\}$ Let's say that $w^R$ is the string obtained by ...
3
votes
2answers
180 views

Compute 'insertable' letters in a regular language

Let $L$ a regular language and define the subsequence closure of $L$ as $\qquad \displaystyle S(L) = \{ w \mid \exists w' \in L.\ w \text{ subsequence of } w'\}$. The problem I want to solve is to ...
3
votes
1answer
1k views

What is the purpose of k in the transitive closure method?

When converting a DFA to a regular expression using the transitive closure method, what is the significance of state $k$ and what values $k$ takes? If $k$ represents the intermediate states then what ...
2
votes
3answers
3k views

NFA for binary words that do not end in 10

Construct an NFA over $\{0, 1\}$ whose language contains only words that do not end with $10$. This is one of the first problems in the book, so it's supposedly easy. I just can't figure it out. It's ...
4
votes
1answer
273 views

Pumping Lemma: is it valid to "multiply the product of powers" in this case?

I need to show that $\qquad \displaystyle S = \{(10^p)^m \mid p \geq 0, m \geq 0\}$ is not a regular language using pumping lemma. Can I multiply the product of the powers and express it to: $S = \...
2
votes
2answers
592 views

Counting with constant space bounded TMs

The problem, coming from an interview question, is: You have a stream of incoming numbers in range 0 to 60000 and you have a function which will take a number from that range and return the ...
26
votes
3answers
2k views

What are the conditions for a NFA for its equivalent DFA to be maximal in size?

We know that DFAs are equivalent to NFAs in expressiveness power; there is also a known algorithm for converting NFAs to DFAs (unfortunately I do now know the inventor of that algorithm), which in ...
16
votes
2answers
4k views

Are regular expressions $LR(k)$?

If I have a Type 3 Grammar, it can be represented on a pushdown automaton (without doing any operation on the stack) so I can represent regular expressions by using context free languages. But can I ...
6
votes
1answer
252 views

regular expression given the language

The language is: $$ L = \{ (a^n) (b^m) \mid n + m = 3k, k \ge 0 \} $$ My attempt at an answer: $$ (a \cup b)^{3k} $$ This will work if the a OR b can change for each instance in the string that is (...
1
vote
1answer
535 views

A regular expression for a given formal language

I wanted to ask if someone can help me to construct a regular expression over the alphabet $\{a,b,x\}$ for the language $L$ which is constituted by all strings containing an odd number of $a$'s, and ...
0
votes
2answers
3k views

Are supersets of non-regular languages also non-regular?

I have to proof that if $L_1 \subset L_2$ and $L_1$ is not regular then $L_2$ it not regular. This is my proof. Is it valid? Since $L_1$ is not regular, there does not exists a finite automata $M_1$ ...
9
votes
3answers
2k views

How to feel intuitively that a language is regular

Given a language $ L= \{a^n b^n c^n\}$, how can I say directly, without looking at production rules, that this language is not regular? I could use pumping lemma but some guys are saying just looking ...
1
vote
0answers
63 views

Show that a language is not regular using the Pumping Lemma [duplicate]

Possible Duplicate: How to prove that a language is not regular? Given a language $L = \{a^pb^{2p} \mid p \ge 1\}$, how could I show, using the Pumping Lemma that $L$ is not regular?
8
votes
1answer
11k views

Relation between simple and regular grammars

I am reading "An Introduction to Formal Languages and Automata" written by Peter Linz and after reading the first five chapters I face below problem with simple and regular (especially right linear) ...
4
votes
2answers
4k views

Why is this example a regular language?

Consider this example (taken from this document: Showing that language is not regular): $$L = \{1^n \mid n\text{ is even}\} $$ According to the Pumping Lemma, a language $L$ is regular if : $y \ne ...
1
vote
1answer
485 views

Non-regular Languages? [duplicate]

Possible Duplicate: How to prove that a language is not regular? Why $L_a$ and $L_b$ are not reguluar? $L_a = \{ e^i f^{n-i} g^j h^{n-j} : n \in N, 1 \leq i, j \leq n \}$. $L_b= \{nm^{i_1} ...
6
votes
4answers
482 views

Why does $A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$ generate a context free language for regular $L$?

How can I prove that the language that the operator $A$ defines for regular language $L$ is a context free language. $A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$, where $x^R$ is the ...
14
votes
2answers
2k views

Closure against right quotient with a fixed language

I'd really love your help with the following: For any fixed $L_2$ I need to decide whether there is closure under the following operators: $A_r(L)=\{x \mid \exists y \in L_2 : xy \in L\}$ $A_l(L)=\{...
5
votes
1answer
373 views

Closure against the operator $A(L)=\{ww^Rw \mid w \in L \wedge |w| \lt 2007\}$

I would like your help with the following question: Let $L$ be a language, and operator $A(L)=\{\,ww^Rw \mid w \in L\ \wedge\ |w| \lt 2007\,\}$ where $x^R$ is the reversed string of $x$. Which of ...
5
votes
1answer
1k views

Chomsky normal form and regular languages

I'd love your help with the following question: Let $G$ be context free grammar in the Chomksy normal form with $k$ variables. Is the language $B = \{ w \in L(G) : |w| >2^k \}$ regular ? ...
10
votes
4answers
2k views

Words that have the same right- and left-associative product

I have started to study non deterministic automata using the book of Hopcroft and Ullman. I'm stuck in a problem that I found very interesting: Give a non deterministic finite automaton accepting ...
3
votes
1answer
918 views

Null Characters and Splitting the String in the Pumping Lemma

So I'm really struggling with the pumping lemma. I think most of my problems come from not understanding how you can and can't split the string in a pumping lemma question. Here is an example, take ...