The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
2answers
39 views

Subset of A Regular Language

I need to show that a subset of a regular language is regular or not. I think it may not be regular but I could not find a counter example. Do you have any simple example to prove that? Thanks in ...
1
vote
1answer
31 views

Regular languages that are stutter-invariant but not star-free (LTL/FO-definable)

I am looking for simple examples and/or general ideas on regular languages (I am interested in finite words and infinite words alike) that are stutter-invariant (a language $L$ over an alphabet $A$ is ...
0
votes
2answers
54 views

Can one prove that a language is regular without having a regular expression?

I was wondering if one could prove that a language is regular without showing a DFA/NFA or a regular expression that expresses it. For example: $L = \{w \in \Sigma^* : w \text{ has at least two ...
0
votes
2answers
25 views

Regular Language Operation

I need to show that the given regular language is closed under the following operation. For example: AllSuffixes(L) = {v : uv in L for some u in (0+1)* } I do not ...
0
votes
2answers
98 views

If given a regular language, how can we prove that a sub-language is regular?

This question has been quite confusing me. $\sum = \{a,b,c\}, L \text{ is a regular language}$ and we have to prove that $L^{'} = \{w \in L : w\text{ containts at least one c} \}$ is regular. What ...
1
vote
2answers
53 views

Is $\{w \in \Sigma ^* : |w|_2 mod 4 = 2\}$ a regular language?

Given alphabet $\Sigma = \{1,2,3\}$, is $\{w \in \Sigma^* : |w|_2 \bmod 4 = 2\}$ a regular language? I tried so hard on finding a regular expression but couldn't...
0
votes
1answer
154 views

When does infinite intersection preserve a closed property?

There are two statements well known in Math and Computer Science: Intersection of infinite number of regular languages is not regular. Intersection of infinite number of convex sets is convex. ...
0
votes
1answer
279 views

Show 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? Let Σ = {0, 1}. Let L = {ww|w ∈ Σ*} I am not sure where ...
0
votes
1answer
36 views

$L$ is a class of languages that cannot be represented by a regular expression. How to state cardinality of $L$.

$L$ is a class of languages that cannot be represented by a regular expression. The book says that the cardinality of $L$ is $2^{\aleph_0} > \aleph_0$ what's the logic behind getting the ...
2
votes
1answer
33 views

Regarding regular expression. why do the following strings not exist in the expression.

Let L be the language defined by the regular expression: (a U b U c)((ab U ac U b)*(a U b) U (aa)*) the answer book says that 'aaaa' and 'aaaaaa' do not belong to L. I can show that aaaa and aaaaaa ...
1
vote
1answer
42 views

set of all reg exp vs set of all languages

$\Sigma$ = {a,b,c,d,e} V = {A,B,C,D,E,F,G,H} According to the notes: The set of all regular expressions over $\Sigma$ is infinite and countable. The set of all languages over $\Sigma$ is infinite ...
0
votes
1answer
37 views

Is this language regular ? [automata]

Is this a regular language : $$L = \{w : w \in \{a,b\}^*\text{ and }abw = wba\}$$ Does my automata only need to start with $a$ and $b$, then loop on $a,b$ and finish with $b\to a$, or do I don't ...
0
votes
2answers
41 views

Let $L$ be the language defined by the regular expression $(a \vee b \vee c)(a \vee b \vee c)$

1) How does $|L| = 9$? 2) $|L^*| = \aleph_0$? Thank you
0
votes
1answer
43 views

The pumping theorem and regular language

I have this problem: $L_0 = L(a^*bba^*)$, the language of the regular expression $a^*bba^*$ $L_1 = \{uu \mid u \in L_0 \}$ Is $L_1$ a regular language? I know that I should use the pumping ...
0
votes
2answers
112 views

Pumping Lemma to show a language is not regular

Let $\Sigma = \{a, b\}$. Use the Pumping Lemma to show that $\mathcal L = \{ a^pab^q: p < q \}$ is not regular. Not sure how to apply PL here, if someone can give some direction.
0
votes
0answers
18 views

How to say “Take result X from the following simultanious calculation and multiply by z” in one equation?

If I have a simulataneious equation, for example: { 5x+10y=3 10x+5y=4 } so the person solving the exuation would need to calculate X and Y (1/3 and 2/15 ...
1
vote
1answer
35 views

Post-concatenation of the languages represented by the null set

I have a small question regarding concatenation of regular languages: Is it true that the concatenation $L\varnothing$, where $L$ is any regular language, result in $\varnothing$? Namely, does ...
0
votes
2answers
38 views

Are those two regular languages the same?

Given an alphabet of {a,b} where Na denotes the number of occurrences of a, and Nb the number of occurrences of b: ...
1
vote
1answer
133 views

Pumping lemma $L=\{a^ib^j | i \neq j ; i,j \ge 0\}$ [duplicate]

So, let's have language $L=\{a^ib^j | i \neq j ; i,j \ge 0\}$ I have to prove that it's not regular. \begin{align} \omega=a^nb^{n+1}=a^{n-1}ab^{n+1} \end{align} \begin{align} x&=a^k\\ y&=a\\ ...
1
vote
2answers
120 views

interpreting language for finite state machine

Can someone explain to me what this means in clear english and maybe give me a hint for how to make a NDFSM (non-deterministic finite state machine) that accepts this language? I understand that the 3 ...
1
vote
1answer
80 views

Constructing a parallel composition from a given transition system and automaton

I am looking at an exercise, where it asks me to construct a parallel composition from a given transition system and an automaton. The transition system looks like this: and the automaton (with ...
4
votes
2answers
119 views

Number of states required to recognize $\{ ss : s \in \{ 0 , 1 \}^*, |s| = i \}$ and its complement

$$\Sigma = \{0,1\}\;\\ S_{i} = \left\{ss: s\in {\Sigma}^{*} \text{and $s$ has length $i$}\right\}$$ Prove that for any $i$, any DFA recognizing $S_{i}$ must have $2^{i}$ or more states. Design a ...
10
votes
2answers
103 views

Mystery Men Movie - Propositional Logic

In the movie Mystery Men, there is this scene: Captain Amazing (good guy): I knew you couldn't change. Casanova Frankenstein (bad guy): I knew you'd know that. Captain Amazing: Oh, I know. And ...
2
votes
1answer
152 views

A variation on counting Balanced Brackets

While counting the number of balanced bracket expressions of length $2n$, the constraint is that for every prefix substring: $$\text{[number of occurrences of (]} - \text{[number of occurrences of )]} ...
0
votes
1answer
284 views

Does closure under the union and concatenation operations imply closure under the star operation?

Given any two languages $A$ and $B$, recall the following regular operations: Union: $A \cup B = \{x \mid x \in A \text{ or } x \in B\}$ Concatenation: $A \circ B = \{xy \mid x \in A \text{ ...
1
vote
2answers
316 views

Constructing a finite automata from a subset of its language

I am attempting to solve the following problem: Let $M=(Q,\Sigma,\delta,q_0,F)$ be a deterministic finite automata which accepts $L(M)$, and let $E$ be the subset of $L(M)$ consisting of all words of ...
1
vote
2answers
76 views

The Relation of Cellular Automata to Languages

In Conway's Game of Life, would a cell be considered a deterministic finite automata? Is there a language for the automata, and would it be a regular language? In probabilistic cellular automata, are ...
0
votes
1answer
50 views

Connection of closed subsets of $A^{\omega}$ and deterministic Büchi-Automata, Question from Book: Infinite Word by D. Perrin & J.-E. Pin

In the Book Infinite Words (homepage) it is proofed that: If $X \subseteq A^{\omega}$, then regarding the Cantor-Topology, the following is equivalent: (1) $X$ is closed (2) $X$ is recognized by a ...
1
vote
1answer
58 views

Is there an (explicit?) bijection from the set of all automatons to the set of all regular expressions that conserves the recongnised language

Let $\Sigma$ be an alphabet, $R$ be the set of regular expressions on $\Sigma$ (that is, trees with leave's values in $\left\{\varepsilon\right\}\cup \Sigma$ and three types of interior nodes, one ...
0
votes
1answer
156 views

Question on NP and its closure properties

Is this true or false? If $L_1$∈ NP and $L_2$∈ NP, then $L_1$∩ $L_2$ ∈ NP. NP = nondeterministic polynomial
1
vote
2answers
64 views

Trying to describe this Turing Machine

Let's say I have the following turing machine: $F_n$ = {M | M is a TM and |L(M) ≤ n} In english, for some given natural number n, $F_n$ is the language of all turing machines that accept no more ...
0
votes
1answer
72 views

Need help with this regular language proof

I'm trying to prove that if $L$ is regular, then $L_S$ is regular as well. $L_s$ = {$x$ | $∃$ $w ∈ Σ^*$ such that $wx∈L$} I know one way to do this would be to create an NFA that accepts $L$, then ...
2
votes
0answers
49 views

Expressiveness of finite memory programs

Assume we have a simple programming language with while, if, := (assignment), ...
3
votes
1answer
185 views

Formal Reduction: Pushdown Automata recognizing context free languages with bounded stack

I am studying for an exam in automata theory and I am having trouble solving the following: Consider pushdown automata and context free languages. Show that the following decision problem is ...
1
vote
0answers
48 views

Systematic way of creating the complement of a regular grammar?

Regular languages are closed under complement. And any regular language can be generated using a regular grammar. Is there a systematic way to create the rewrite rules for the complement of a regular ...
7
votes
5answers
442 views

A computer's memory is finite, so how can there be languages more powerful than regular?

A computer has a finite memory. There are no computers with infinite memory. Therefore the only languages that a computer can process are those whose member strings are finite. As I recall, the ...
2
votes
1answer
113 views

Why do complex grammars require powerful algorithms?

I am reading a fabulous book on Formal Languages and in the book it says: As the rewrite rules of a grammar become more complex, the algorithm for recognizing the associated language becomes ...
1
vote
0answers
41 views

Regular Functional Algorithms

A language is regular if it is accepted by a read-only Turing machine. I am curious about applying this model to functional problems rather than decision problems. Definition: A functional read-only ...
1
vote
1answer
81 views

Proving a language is not regular using pumping lemma

I had an exam today and the professor gave us the following problem: Let $L = \{a^nb^m : n|2m \}$. Prove that $L$ is not regular. Ok this sounds easy. Here is my solution: Assume opposite -- $L$ is ...
0
votes
1answer
153 views

Is this language regular?

Given $m,n∈Z$, A is a finite alphabet set ,and $L=\{(a^m,a^n)\}^*$ is subset of $A^*\times A^*$ . Is this language regular ? For example, is $L=\{(a^3,a^7)\}^*$ regular ? Here L is not the set ...
2
votes
2answers
51 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 ...
0
votes
1answer
92 views

Pumping Lemma Proof for $ww$

The proof of language $F = \{ww\mid w ∈ \{0,1\}^*\}$ is not a regular language using pumping lemma most of the solutions i found uses the string $0^p10^p1$. I understand the proof using that. But in ...
4
votes
2answers
84 views

Prove that $\{1, 11, 1001,\dots\}$ is an irregular language

Let $L:=\{1, 11, 1001,\dots\}$ be the language with alphabet $\{0,1\}$ which is formed by all powers $3^n, n=0,1,\dots$ written in binary notation. How to prove that $L$ is not regular?
1
vote
1answer
91 views

Give a regular grammar for L

Give a regular grammar for L= {a^n b^n : n<=100} I would do something like this : S---> A | empty string A---> aB| empty String B---> Ab but How do we keep count of the number in the grammar? ...
3
votes
0answers
658 views

Pumping lemma for $a^nb^{2n+1}$

I know how to solve pumping lemma for $a^nb^n:n\geq 0$. But I don't understand how can I solve this example : $a^nb^{2n+1}:n\geq 0$. I tried to solve it but I am not sure that I have solved it ...
0
votes
2answers
142 views

Prove $L=\{ 1^n| n\hspace{2mm}\text{is a prime number} \}$ is not regular.

Prove $L=\{ 1^n| n\hspace{2mm}\text{is a prime number} \}$ is not regular. It seems to use one Lemma: Pumping Lemma.
3
votes
2answers
1k views

Are regular languages necessarily deterministic context-free languages?

The original problem Suppose M is DCFL (Deterministic Context Free Language) and N is a regular language. Answer the following questions and justify your answers. a) Is M-N necessarily context-free? ...
2
votes
2answers
48 views

If $\{w^k|w\in L\}$ regular implies L regular?

If L is a language and the language $$\tilde{L}:=\{x^k,x\in L, k\in\mathbb{N}\}$$ is regular, does that imply that L is regular? ($|L|<\infty$ gives equivalence) We came across this question when ...
1
vote
2answers
36 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 ...
0
votes
1answer
80 views

Algorithm for checking if regular language has given property

Give an algorithm that will decide (in any finite time) if given regular language $L$ (given by some regular expression) has given property: $$\forall_{x\in L} \exists_{y\in L} \left( \left(x\neq ...