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

learn more… | top users | synonyms

0
votes
0answers
9 views

Prove that L = {ww | w ε 0*10*} is not regular

Using pumping lemma on this, I am having some trouble assuming an S... If I had for example L = { ww | w ε {0, 1}* } I'd assume ...
0
votes
1answer
18 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
24 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
82 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
37 views

How do I show that {a^nwb^n:..} is not regular?

$\ \sum= \{a,b\} $ Show that: $ L:= \{a^nwb^n: m,n \in \mathbb N, m\geqslant n, w\in\sum^m\} $ is not regular. I'm trying to proof this with the Pumping Lemma, but I'm kind of confused because of the ...
0
votes
1answer
34 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
48 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
44 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 ...
0
votes
1answer
49 views

Three languages and how to decide if they are regular

From following languages which one is regular and why others are not?And what is the regular expression for regular one. $L_1= \{wxwy | x,y,w \in (a+b)^+\}$ $L_2 = \{xwyw | x,y,w \in (a+b)^+\}$ ...
1
vote
1answer
43 views

Is it Regular Language?

According to Wikipedia, Regular Language is Recognized by Some DFAs, or expressed by Regular Expression .. and all finite Language are regular but, not all regular is finite .. that's mean it may be ...
-1
votes
1answer
39 views

Create CFG and pushdown automaton for {ww} [duplicate]

I've been trying to make a CFG, a pushdown automaton and a regular expression for the language $\qquad L(M) = \{ww : w \in \{a, b\}^*, |w| \text{ is even}\}$. I understand how the reverse of the ...
1
vote
2answers
45 views

L ={ $a^{m^n}$ | $m$>$n$ } is Regular or not by pumping Lemma [duplicate]

L ={ $a^{m^n}$ | $m$>$n$ } I am bit confuse whether to consider this language as L = $(a^{m})^{n}$ OR L = $a^{\left(m^n\right)}$. If it is considered as L = $(a^m)^{n}$ then want to check it ...
0
votes
2answers
29 views

Automaton accepting $\{a^{2i}bc^{2k} \mid i, k \in\mathbb{N}\}$

How can I produce an automaton accepting $\{a^{2i}bc^{2k} \mid i, k \in\mathbb{N}\}$? I am essentially confused about exactly what the $2i$ and $2k$ mean. Does that mean that the automaton only ...
0
votes
2answers
33 views

Intersection of regular and not regular

$L_1=\{a^n\mid n\ge1\}$ is regular and $L_2=\{a^{n^2}\mid n\ge1\}$ is non-regular. We know that $L_1\cap L_2$ is regular but, here $L_1\cap L_2=L_2$; and $L_2$ is not regular. How is this possible?
0
votes
2answers
43 views

Kleene closure, concatenation problem

If $L_1 = \emptyset$ , $L_2= \{a\}$ then what is $$L_1\cdot L_2^* \cup L_1^*$$ The answer given is $\{\epsilon\}$ but I think it should be $\{\epsilon,a\}$. My Approach : $L_1^* = \{\epsilon\}$ ...
3
votes
3answers
99 views

Was there an attempt to make reusable regular expressions?

In everyday practice I often encounter tasks which would benefit from being able to define aliases for chunks of regular expressions to reuse them later. Typical examples include: parsing a floating ...
4
votes
0answers
50 views

context free grammar to NFA

I've been given an exercise to solve which goes as follows: generate an NFA from the given CFG, $$\begin{align*}S &\to AB \mid c\\ A &\to aAb \mid c\\ B &\to bBa \mid c\ . \end{align*}$$ ...
0
votes
1answer
34 views

Give an example of a non-regular language $L$ such that $L^*$ is regular [duplicate]

I can't think of an example of a non-regular language $L$ such that $L^*$ is regular. . Any help ?
2
votes
1answer
71 views

Language of binary strings divisible by 7

There was a question something like, "Consider the language of all integers converted to binary form. The language of all strings divisible by 7 is : 1) Recognizable by a finite-automaton. 2) ...
3
votes
1answer
20 views

Automata for languages derived from an automaton by number of state visits

My question in response to this answer: what would the finite automata look like for $L_1$ and $L_0$ in the answer? I get how the languages are formed; however, since $M_L$ cannot remember how many ...
2
votes
1answer
46 views

Finite Automata — Determine if a set is regular

I have been at this for hours. The question is: Prove that the language $A = \{0^kx \mid k > 0, x \in \{0,1\}^*, \text{ and } \#(0,x) \geq k\}$ is regular, where $\#(n, x)$ denotes the ...
2
votes
1answer
109 views

are regular languages closed under division

I am trying to solve this question which appeared in previous exam paper Can someone help me what i am failing to understand For languages $A$ and $B$ define $A \div B = \{x \in \Sigma^{\ast} : xy ...
2
votes
1answer
88 views

regular expression for binary language has at least one 1

So I had an exam in the subject "Theory Of Computation" and one of the questions was to write down a regular expression of a binary language that has at least one (1) , my answer was : 0* 1 0* (0* 1 ...
2
votes
1answer
54 views

How to prove that the Myhill-Nerode equivalence classes for L are the same as for its complement?

Given language $L$, I want to show that its Myhill-Nerode equivalence classes are the same as for its complement $\overline{L}$. I am thinking of constructing a DFA $M$ for the Language $L$ so the ...
0
votes
1answer
27 views

prove decidability and recognizability

I want to prove that for any language $L_1$ described by a Turing machine and any regular language $L_2$, $L_1 \cap L_2$ is described by a Turing machine that its recognizability and decidability is ...
18
votes
3answers
3k views

Can regular languages be Turing complete?

I was reading about Iota and Jot and found this section confusing: Unlike Iota, where the syntactic tree for a string can branch either on the left or on the right, Jot syntax is uniformly ...
1
vote
1answer
43 views

If pref(L) is regular, does that imply L is regular?

I have this exercise for homework: Say we have a language L. we know that the language pref(L) (all the prefixes of ...
2
votes
1answer
60 views

Help on using the pumping lemma?

I'm trying to prove that a language is not regular. That language is: {w ∈ {a, b}* | amount of a's in w is equivalent to the amount of b's in w, mod 2}. I have an inkling that this language is not ...
-2
votes
1answer
41 views

NFA: Regular Language that starts with ab but does not end with ab?

$L = \{x \in \{a,b\}^* \mid \text{$x$ starts with $ab$ but does not end with $ab$}\}$ I'm having trouble making a table for this NFA. I tried a few sketches out of the diagram and I can post them ...
1
vote
1answer
80 views

How to write a DFA where the second digit is equal to the last digit of binary strings?

I'm having some trouble writing a DFA for the language $$\{w =b_1\dots b_k \in\{0, 1\}^* \mid b \ge 2 \text{ and } b_2=b_k\}\,.$$ What I thought for this is writing a DFA where there are 4 states, ...
1
vote
1answer
28 views

Proving a language is not regular [duplicate]

I need to prove that the following language is not regular $\{c^mb^na^n \mid n>0,m\geq0\}$ But I am not sure how to do that for this particular one. I vaguely understand pumping lemma, but ...
-1
votes
1answer
46 views

Prove a language is regular [duplicate]

I am asked to find Prove that the following languages are regular languages: (a) $\{a^nb^ma^k \mid n\geq3,m\geq1,k\geq1\}$ (b) $\{a^n \mid n\neq3 \text{ and } n\not\equiv2 \mod7\}$ ...
0
votes
0answers
11 views

Proving a language is regular [duplicate]

I am asked to find Prove that the following languages are regular languages: (a) $\{a^nb^ma^k \mid n\geq3,m\geq1,k\geq1\}$ (b) $\{a^n \mid n\neq3 \text{ and } n\not\equiv2 \mod7\}$ ...
-4
votes
1answer
46 views

Show whether the language with almost as many 0 as 1 in every prefix is regular [closed]

This is the exercise: Let A be a language defined over the alphabet Σ = {0, 1} composed by the strings with the property that in every prefix, the number of 0s and the number of 1s differ by at ...
1
vote
5answers
759 views

Show that every infinite language has a non-regular subset

I'm trying to solve this problem: Let $L$ be some infinite language, show that there exists a sub-language of $L$ that is not regular But can this be correct? If I have the language $\{a\}^*$ ...
3
votes
1answer
46 views

The language of any constant-time Turing machine is regular

Suppose we have a Turing machine $M$ so that there is a constant $t$ such that the Turing machine always runs in time $t$ or less. Prove that the language of $M$ is regular. This seems to be a ...
1
vote
1answer
58 views

When using the Pumping lemma, how do I deal with different cases of y?

I want to prove L is not regular:$$L={\{www|w \in \Sigma^*\}}$$ $$\Sigma=\{a,b\}$$ I am sure I can do so using pumping lemma. I used $$ab^pab^pab^p$$as my chosen string but I am stuck. I do not know ...
0
votes
0answers
16 views

Regualr Expression for C comments [duplicate]

I hope you can help me right now, I am working on lexical analyzer for C language, I am bit confuse bout the regular expression of C style comments. a regex which can handle both single and multiline ...
1
vote
1answer
119 views

Show that a regular language L contains only palindromes if and only if all words of length at most 3n are palindromes

This is an extension of a previous question asked by a different user earlier: Let $x, u, v, w, y, x', u', v', w', y'$ be words satisfying $y'x' = xy$. $y'u'x' = xuy$. $y'v'x' = xvy$. ...
2
votes
1answer
40 views

Pumping lemma for 0^n and n>0

When applying the pumping lemma to $L = \{ 0^n \mid n>0\}$ I do the following: $S = 0^p$ $x = \varepsilon$ $y = 0^p$ $z = \varepsilon$ so $S = xyz = (\varepsilon)0^p(\varepsilon)$ For $x y^i z$ ...
0
votes
2answers
49 views

Help designing a Turing Machine

I am faced with the following question: Design a Turing Machine that recognizes the language $L = \{1^{2n+1}\mid n \text{ is a non-negative integer}\}$. Show the state diagram. I started doing ...
0
votes
2answers
77 views

High Level Explanation of the Pumping Lemma

I have a problem that I cannot figure out regarding using the pumping lemma to prove that a language is not regular. I don't understand how I go about proving through contradiction that the language ...
0
votes
1answer
52 views

How to prove that $\{0^n 1^{5n} \mid n \ge 10000 \}$ is not a regular language?

I proved that $$ \{ 0^n 1^{5n} \mid n \geq 0 \}$$ is not a regular language using Pumping Lemma by following way. Solve by contradiction that $ L = \{0^n 1^{5n} \mid n \geq 0 \}$ is regular ...
5
votes
2answers
277 views

Detecting palindromes in binary numbers using a finite state machine

In my first algorithms class we're creating these patterns that are supposed to model a finite state machine. We were given a task to think if we can figure out a way to detect palindromes in binary ...
3
votes
2answers
90 views

If $L$ is regular, must the language $L_1 = \{w : w^Rw \in L\}$ be regular, or may it be non-regular?

The reverse, $w^{R}$, of a string $w = w_1w_2...w_n$ is the string $w_n...w_2w_1$. Suppose that L is a regular language. Must the language $L_1 = \{w : w^Rw \in L\}$ be regular, or may it be ...
3
votes
1answer
59 views

Showing that A' is a regular language

Let $\Sigma = \{0,1\}$, and suppose that $A$ is a regular language. Define $$A' = \{ u \mid \exists a, b \in\Sigma: abu \in A\}$$ i.e., $A'$ is obtained from $A$ by taking every string in $A$ and ...
-1
votes
1answer
48 views

Equivalence of some Automata & Language & NFA

I read some note about Automaton Course. i see this note, that following all is the same. but i think the L(g) is not equal to NFA and regular expression. anyone could help me with defining the ...
3
votes
2answers
43 views

Finding out if languages involving counting and modulo operations are regular

I am having trouble with the regularity of the two following languages: i) $\{0^{n}1^{m}|n,m>0,n-m=0\,mod\,3\}$ ii) $\{0^{n}1^{m}|n,m>0,n+m=0\,mod\,3\}$ To clarify this is stating that the ...
3
votes
2answers
487 views

If both the concatenation of two languages and the second “half” are regular, is the first too?

Given that $L_2$ is regular and infinite and $L_1 \cdot L_2$ is regular, then $L_1$ is also regular. I need some help on getting started on proving this is the case. My intuition is that if $L_1 ...
2
votes
3answers
120 views

Prove that the equal-length concatenation of regular languages is context free

If A and B are regular, then prove that $A@B = \{xy \mid x \in A \text{ and } y \in B \text{ and } |x|=|y|\}$ is always context free. So I'm trying to come up with the proof that looks something like ...