Tagged Questions

2
votes
1answer
24 views

Regular composition of non-regular language

I've got the following problem: Let's take language $L$. Is it posible that $L$ is not regular itself, but it's composition $L\cdot L$ becomes regular? I suspect that's correct, yet I ...
1
vote
2answers
26 views

Proving irregularity of a language

While learning about formal languages, I found the following problem: Let us consider words over the alphabet $\lbrace 0, 1\rbrace ^3$. We say that a word $\langle a_1, b_1, c_1 \rangle \ldots ...
1
vote
2answers
80 views

Infinite union of finite unions

Is the following sound reasoning, and if so, why? Letting $S$ be a language over the alphabet $\Sigma$, $$ \bigcup_{i=0}^{\infty}\left(\bigcup_{k=0}^{i-1}S^k\right) = \bigcup_{i=0}^{\infty}S^i $$
2
votes
2answers
57 views

Giving a regular grammar for the language

I am trying to brush up on my regular grammar knowledge to prepare for an interview, and I just am not able to solve this problem at all. This is NOT for homework, it is merely me trying to solve ...
2
votes
1answer
77 views

Pumping Lemma problem

Apply pumping lemma to each of these and prove that they are not regular. $L = \{ (0^p)(1^q)2 \mid 0 < q < p\}$ $L_2 = \{ (a^p)(b^q)(c^r) \mid p = q \text{ or } q = r\}$ Here my ...
0
votes
1answer
39 views

Interesting problem on finding a Regular Expression for a language

Lets say we have some language P such that P = {z^n } where n is not divisible by 10. Give a regular expression for this language and then a generalized regular expression thats shorter than the ...
3
votes
1answer
59 views

Does the Halting Problem apply when evaluating programs that are regular languages?

Here is my understanding of the Halting Problem: It is impossible to write a program H that can determine for any arbitrary program ...
1
vote
1answer
100 views

If $L$ is regular, prove that $\sqrt{L}=\left\{ w : ww\in L\right\}$ is regular

Let $L$ be a regular language. Prove that $\sqrt{L}:=\left\{ w : ww\in L\right\}$ is also a regular language. I suppose I need to modify state machine for $L$ to accept $\sqrt{L}$, but I've been ...
1
vote
1answer
87 views

Prove that if $ L $ is a regular language over the alphabet $ Z = \{ 0,1 \} $, then $ L' = \{ax \mid x \in L \} $ is also regular for any a in $Z$.

Prove that if $L$ is a regular language over the alphabet $Z = \{0,1\}$, then $L' = \{ax \mid x \in L\}$ is also regular for any $a \in Z$. I'm not sure how to even begin on this one. If even a ...
0
votes
1answer
75 views

The regularity of Markov chains with a threshold

I am studying Paz's "Introduction to Probabilistic Automata", and there is an exercise I cannot solve: Ex. 11, p. 170: Prove that the number of nonregular events of the form $\{x \mid p^A(x) > ...
3
votes
2answers
208 views

Question about regular languages and finite automata

We say a language $L$ is regular if it is accepted by some finite automaton $M$. I would like someone to clarify this definition. Given a finite automaton $(Q, \Sigma, \delta, q_0, F)$, we define the ...
1
vote
2answers
52 views

Prove that any finite set of words is regular. How many states is sufficient for a single word $w_1…w_m$?

DFA Prove that any finite set of words is regular. How many states is sufficient for a single word $w_1...w_m$? For part 2, wouldn't it require M states if the word length is M?
1
vote
2answers
37 views

Proving a language to be regular

Let $\Sigma_{2}={ \begin{bmatrix} 0\\ 0 \end{bmatrix}, \begin{bmatrix} 1\\ 0 \end{bmatrix},\begin{bmatrix} 0\\ 1 \end{bmatrix},\begin{bmatrix} 1\\ 1 \end{bmatrix}}$ ...
2
votes
2answers
162 views

Pumping Lemma Excercise

I am having a really tough time proving the following language is not regular using the pumping lemma. This whole time I have been working on pumping lemma problems, the variable of the power has been ...
2
votes
1answer
134 views

Proving a language is regular or irregular

I am having a really difficult time writing proofs for these problems. I would greatly appreciate any suggestions for a strategy on how to look at such problems and begin writing a proof. Trying to ...
4
votes
2answers
103 views

Pumping Lemma proofs

I am having a hard time writing a Pumping Lemma contradictory proof for the below statements. 1) $L_1 = \{ ww \mid w \in E^* \}$ <--- I don't understand how to read this. This is what I tried: ...
2
votes
0answers
164 views

Regular, Context-free, Recursive, Recursively Enumerable Language Relationships

I am currently under the believe that all regular languages are context free, thus all regular languages are recursive, and therefore all regular languages are recursively enumerable. If I am given ...
2
votes
3answers
80 views

Pumping lemma contrapositive

I have a few questions about Pumping Lemma Contrapositive. First of all, how do I choose pumping length $n$? Is it just any constant from the language definition? i.e. I have $L=\{a^kb^gc^hd^j\}$ so I ...
0
votes
3answers
430 views

Is there a subset of a non regular language that is regular

I am just curious is there any non regular language whose subset is regular?
0
votes
2answers
49 views

Confusion related to the type 3 grammar

I have this confusion. Lets say I have language produced by type 3 grammar such that L(G1) = <Vn1,Vt,P1,S1> I need to find a type3 grammar G3 such that ...
3
votes
1answer
79 views

Confusion related to the concatenation of two grammars

I have this confusion. Lets say I have two languages produced by type 3 grammar such that L(G1) = <Vn1,Vt,P1,S1> L(G2) = <Vn2,Vt,P2,S2> I need to ...
4
votes
3answers
132 views

Deciding equivalence of regular languages

Given two regular expressions $R$ and $S$ on an alphabet $\Sigma$ it is possible to decide their equivalence as follows: build two finite automata $M_R$ and $M_S$ such that $L(R) = L(M_R)$ and $L(S) ...
2
votes
1answer
106 views

Is the set of codes of Deterministic Finite-State Automata a regular language?

Let $\Sigma$ be a given alphabet. Is there a way to code up Deterministic Finite state Automata (DFA) over $\Sigma$ as strings of $\Sigma$ in such a way that the corresponding subset of $\Sigma^*$ is ...
2
votes
2answers
449 views

How to guess whether a language is regular or not

I have a few languages and I am not given whether they are regular or not. If I had to prove their irregularity, then it would not have been difficult. How do I go about finding if the language is ...
0
votes
3answers
163 views

Different version of pumping lemma and how to prove it

I have a question to solve but I am not even getting a direction to start or how to narrow down this problem. Please provide in your inputs. Consider the following version of pumping lemma. For any ...
6
votes
3answers
129 views

Reductions for regular languages?

To reason about whether a language is R, RE, or co-RE, we can use many-one reductions to show how the difficulty (R, RE, or co-RE-ness) of one language influences the difficulty of another. To reason ...
2
votes
2answers
215 views

The language that contains no proper prefixes of all words of a regular language is regular

Let $L$ be a regular language. I need to prove that the language $$M_L = \{w \in L \; | \forall x \in L \; \forall y \in \Sigma^+ : w \neq xy \}$$ that contains all words of L that do not have a ...
4
votes
1answer
54 views

Proving that a language build from two regular languages is regular as well

Let $L, M \subseteq \Sigma^*$ be regular languages. I need to prove that $$N = \{x \in \Sigma^* \; | \; \exists y \in L : xy \in M\}$$ is as well a regular language. My favored approach is to find a ...
2
votes
1answer
25 views

Finding the mistake in a new way of generating FSMs from regular expressions

As described e.g. here (see pp. 2-3) a final state machine can be easily constructed from a regular expression. For the union of to expressions $e + f$ I need to look at the original way of ...
2
votes
2answers
53 views

Proof for the amount of states of a regular language

Let L be a formal language. Two words $u,v \in \Sigma^*$ are called separable if $\exists w \in \Sigma^* : uw \in L, vw \not\in L$. Nerode lemma: Let L be a formal language. If there are $n$ ...
3
votes
2answers
664 views

Application of Pumping lemma for regular languages

I need to proof by using the Pumping lemma that the language $L = \{0^m1^n \;|\; m \geq n\}$ is not regular. According to the Pumping lemma for each regular language a word $w = xyz$ exists, that ...
2
votes
1answer
61 views

Proving that languages are not regular

The Nerode Lemma can be used to show whether a language is regular or not. This can be done in several ways but I need to do it by providing a set of separable items. Example: The language of ...
2
votes
4answers
2k views

Intersection of two deterministic finite automata?

I'm trying to solve a problem where I have to create a DFA for the intersection of two languages. These are: $$\{s \in \{{\tt a}, {\tt b},{\tt c}\}^\ast : \mbox{every ${\tt a}$ in $s$ is ...
1
vote
2answers
117 views

Prove that [ContextFreeLanguage - RegularLanguage] is always a context free language, but the opposite is false

Let L be a context-free grammar and R a regular language. Show that L-R is always context-free, but R-L is not. Hint: try to connect both automata) The above hint did not help me :(
1
vote
1answer
188 views

Algorithm to tell whether a regular language contains at least n strings

I'm taking a course on formal languages and was given this exercise: Give an algorithm to tell whether a regular language $L$ contains at least $100$ strings. Can someone give me a hint? Thanks! ...
0
votes
4answers
119 views

Proving that a language is regular

I want to show that $$L = \{1^a2^b3^c | a + b + c \text{ is even}\}$$ is a regular language. I thought about a final state machine or about defining a grammar, but that didn't work good. Do you have ...
0
votes
4answers
92 views

Proof for formal languages

Prove that for all languages $M,N \subseteq \Sigma^*$ applies: $(M+N)^* = (M^*N^*)^*$ Hi! I do'nt really understand why this applies: The first term uses the Kleene star on the union of M and ...