The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
2answers
161 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?
2
votes
2answers
889 views

suffix regular language

Can someone give me an idea how to prove this: suffix(L) = {y | xy $\in $ L for some x $\in$ $\Sigma$ *}. Or suffix is the set of all suffixes of its strings. Prove that if L is regular, then so is ...
1
vote
2answers
213 views

How to prove that the following language is not regular?

This is the following problem that I've been having difficulty on: For this problem, we will show that there are non-regular languages over the alphabet $\{0\}$. The language that will be used is the ...
1
vote
2answers
72 views

Proving this language is regular?

Is $$L =\big\{x^ny^m : |n-m| = 2\big\}$$ a regular language? I can't seem to figure this question out, and i've tried drawing a dfa but I still can't seem to find it. If there is a possible dfa, ...
1
vote
2answers
58 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}}$ ...
1
vote
3answers
93 views

regular language?

I need help proving whether this language is regular or not. $$L = \big\{ w \mid w \in \{a,b\}^*, n_a(w)\text{ is even}, n_b(w)\text{ is even}\big\}$$ That is, the number of $a$'s is even and the ...
1
vote
1answer
113 views

Question about infinite union of non-regular languages

If none of the languages $L_1$,$L_2$,... is regular, and $L_i \subseteq L_{i+1}$ for each i, is $\bigcup_{n=1}^\infty L_i$ regular? I guess the answer is no for any given languages, but I cannot ...
3
votes
1answer
4k views

Converting to Chomsky Normal Form

I am trying to learn how to convert any context free grammar to Chomsky Normal Form. In the example below, I tried to apply Chomsky Normal Form logic, to result in a grammar, where every symbol either ...
1
vote
2answers
137 views

How can I prove the majority of three languages is also regular if the three languages are regular?

This is a question I've been stuck on recently: Let $A$, $B$, and $C$ be three languages over the same alphabet. Define $\mathrm{maj}(A,B,C)$ to be the collection of all strings $w$ that occur in at ...
1
vote
2answers
81 views

What are the states of this NFA?

I have to realize an NFA that recognizes the language of strings on the alphabet {a, b} ending with: bb, ba, baa. I thought that there must be the following states: $q_0$: the string ends with bb. ...
1
vote
1answer
124 views

Proving this language is not regular

Let $$L = \left\{b^ic^jd^k \mid i \ge 0, j\ge 0, k\ge 0,\text{ if }i=1\text{ then }j=k\right\}\;.$$ I have been trying to get a start on this proof for a long time now with no success. What would ...
2
votes
2answers
257 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
243 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
167 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: ...
0
votes
3answers
2k views

Determine if a language is regular from the first sight

Is there a way to guess if a language is regular from the first sight? I.e. in order to choose proof methods, I have to have some hypothesis at first. Do you know any hints/patterns? I need this to ...
2
votes
1answer
32 views

Regularity of “middles” of words from regular language

I need some help with the following problem: $L$ - regular language and i have to prove that the language $P$ = {$\alpha$| $\beta\alpha\gamma \in L$, $\beta,\gamma \in (A)^*$} is regular. In other ...
1
vote
2answers
628 views

How to prove by pumping lemma these languages are not regular?

$L_1 = (a^k * b^r \mid k \neq r^2)$ $L_2 = (a ^{\sum_i ^n t} \mid n > 0 )$
0
votes
1answer
203 views

Building a regular grammar from NFA

I'm requested to make a regular grammar from a given NFA. In this NFA, there's a "death state", which means, when getting to it, there's no way back to the rest of the states (a self-loop to the same ...
1
vote
1answer
72 views

Proving or disproving regularity of a language

The question is as follows: If L1 and L2 are not regular and L1 ⊆ L ⊆ L2, then L is regular My intuition says that it's wrong so I've been looking for a ...
0
votes
2answers
96 views

following languages regular or not?

Please help me determine if those languages are regular or not. If not, I'll be glad to get a direction to prove it by contraditiction of the pumping lemma: $L = \{a^n\mathord{*} a^m \mid m \equiv ...
0
votes
1answer
38 views

proving by construction that language is regular

I had this exercise saying the following: $$ L =\{w\mid w = w_1xw_2 \land w_1, w_2, x\text{ are words }\land w_1w_2 \in L_1 \land x \in L_2\} $$ I need to prove that $L$ is regular by defining an ...
2
votes
0answers
279 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
143 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 ...
4
votes
1answer
912 views

Myhill Nerode - is language regular or not?

I'm trying to understand how to find equivalence classes of a language to prove its regularity. I think that if I'm able to FULLY understand one example then I will get this topic right. Let's say I ...
0
votes
4answers
106 views

Language over $\{0,1\}$

I am learning about languages but struggling with operations on them. In my book there are some simple examples but how would I for example describe a language over $\Sigma=\{0,1\}$ such that every ...
1
vote
2answers
421 views

Showing that a language is regular - Pushdown Automaton

So what I have to prove is that $L$ is regular given that the stack of PDA for $L$ never grows beyond $n$ entries on any input, and in this case $n=200$.
0
votes
3answers
104 views

showing that a regular language is regular after taking a letter off or after adding letters

I'll be happy to recieve help with this one: Given the regular language $L$ defined over alphabet $\{a,b\}$, show that the following languages are also regular: $\{xy\mid xay\in L\}$ ...
0
votes
1answer
629 views

Formal proof of the concatenation of two regular languages automaton

During an exercise for college, given two NFA's, $A_1\text{ and }A_2$ that accept the languages $L_1\text{ and }L_2$, I've built a NFA, $M$ that accepts the language $L_1*L_2$ (concatenation). The ...
0
votes
1answer
212 views

Regular Language : $\{a^m b^n \mid mn \ge 10\}$

I am little bit confuse here about below language is it regular language $$ L= \{a^m b^n \mid mn \ge 10 \}. $$
0
votes
2answers
225 views

How to deduce Intersection and Difference of these languages?

$\mathcal{L1}=\{a^nb^n c^m d^m\;|\;m,n>=1\}$ $\mathcal{L2}=\{a^nb^n \;|\;n>=1\}$ $\mathcal{L3}={(a+b)^*}$ How to deduce the Intersection of $\mathcal{L1}$ and $\mathcal{L2}$ is CFG or ...
0
votes
3answers
1k 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?
2
votes
1answer
60 views

Is regularity is preserved under reversal?

When talking about languages and regular languages. Can I say that reversal preserved regularity since if the language L is regular, we can generate it by right linear grammar. Therefore, the ...
1
vote
1answer
163 views

regular expression/languages short questions

I'm stuck on these practice problems. If someone could help me solve them it would be great. What is a contextfree grammar for the langauge $L = \{a^i b^j c^j d^i \mid i,j \ge 0\}$ The following ...
0
votes
2answers
131 views

Help with regular expression subset proof

Okay, so basically I'm just showing that two ways to express a regular expression are equal, and to do so, I'm showing they're subsets of each other. The expression is: $(A^*B^*)^* \subset ...
1
vote
1answer
47 views

Why is the languge of same occurences of ab and ba regular?

Let the language $L = \{ s~|~s\text{ has the same number of "ab"s as "ba"s.} \}$ for the alphabet $\Sigma = \{ a, b \}$. Apparently, $L$ is regular. Why? Wouldn't a machine that recognizes $L$ have to ...
2
votes
2answers
44 views

Why is $S(L)$ regular?

Let $L$ be a regular language, and $\Sigma$ be its alphabet. Then, the language $S(L) = \{y \in \Sigma^*~|~xy \in L \text{ for some string }x \in \Sigma^*\}$ is also regular. I am trying to ...
2
votes
2answers
75 views

For the language $\{w \mid w \in \Sigma^*, w \neq \lambda\}$, is the following regular expression correct?

For the language $\{w \mid w \in \Sigma^*, w \neq \lambda\}$, is the following regular expression correct? $(a+b)^+$ . Which is $(a+b)$ to the power of $+$ which I think accepts all combinations of ...
1
vote
3answers
2k views

Formally prove that every finite language is regular

I know how to prove this informally, but don't know what the formal proof should look like.
1
vote
2answers
258 views

Prove that the language $\{ww \mid w \in \{a,b\}^*\}$ is not FA (Finite Automata) recognisable.

Hint: Assume that $|xy| \le k$ in the pumping lemma. I have no idea where to begin for this. Any help would be much appreciated.
0
votes
1answer
115 views

For languages A and B which are both FA recognisable, how do you prove that the concatenation of A and B, A.B is also FA recognisable?

Note: FA = Finite Automaton Given that N1 and N2 are the finite automatas that recognise A and B respectively, I know that N1 and N2 needs to be combined into a new automation N that starts in the ...
1
vote
1answer
916 views

Showing that a language is not regular using Myhill-Nerode Theorem

I'd like to show that the language below is not regular using Myhill-Nerode Theorem. How can I do that? Thanks in advance. Let $Σ = \{0, 1, +, =\}$ and $\mathrm{ADD} = \{x = y + z \mid x, y, ...
0
votes
1answer
213 views

Homework proof Extended Transition Function by mathematical induction

Let M = (Q,∑, q0,A, δ) be an FA. Below are other conceivable methods of defining the extended transition function δ∗. In each case, determine whether it is in fact a valid definition of a function on ...
2
votes
2answers
566 views

Prove that a language B is regular

here is the question I'm dealing with: Let B = {$1^{k}$y|y $\in$ {0,1}* and y contains at least k 1s, for k $\geq$ 1}. Show that B is a regular language. Can I use the pumping lemma to ...
25
votes
6answers
3k views

Is the set of all valid C++ programs countably infinite?

I have heard that the set of valid programs in a certain programming language is countably infinite. For instance, the set of all valid C++ programs is countably infinite. I don't understand why ...
2
votes
2answers
79 views

Is $L = \{\omega : \omega\text{ contains exactly one 'foobar'}\}$ regular?

Is the language $L = \{\omega : \omega\text{ contains exactly one 'foobar'}\}$ regular? I have a hunch that it is non-regular because a regular expression representing the language must remember that ...
1
vote
1answer
93 views

Why is my pumping lemma proof misleading?

I am trying to prove whether $L = \{s : s \text{ contains exactly 1 a}\}$ for the alphabet $\Sigma = \{a, b\}$is regular or not using the Pumping Lemma. I think it is regular because I can construct a ...
0
votes
2answers
62 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 ...
0
votes
1answer
55 views

Confusion related to context free grammar

If G is a context-free grammar such that it has the productions of the form $$ X \rightarrow \alpha Y ,X \rightarrow \alpha $$ How can I show that L(G) is a regular language
3
votes
1answer
120 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 ...
3
votes
1answer
97 views

Does A* = A when A contains an even number of 0s?

In class, my professor proposed the following: Let $A = \{w \mid w \text{ contains an even number of $0$'s} \}$ where $\Sigma=\{0,1\}$ is the alphabet. And then asked the class whether $A^* = A$, ...