Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

Filter by
Sorted by
Tagged with
3
votes
1answer
82 views

Why are regular tree languages closed under intersection, but deterministic context free languages are not closed under intersection?

I am looking for intuition here. Essentially, I understand that the set of parse trees from a context free grammar forms a regular tree language. I also understand that regular tree languages are ...
0
votes
1answer
23 views

Partitions of star-free languages and questions on the proof of the Splitting Lemma by Diekert/Gastin

I'm currently reading a paper on First-order definable languages by Volker Diekert and Paul Gastin. Im having trouble understanding a part of the proof for lemma 3.2 (splitting lemma). The part I'm ...
2
votes
1answer
119 views

Transitions between lexicographical orders

I have six characters: (,),[,],{,}. They are stored lexicographically: '(' < ')' < '[' < ']' < '{' < '}'. So I can store all balanced parenthesis sequences of length $n$ ...
0
votes
1answer
25 views

Words which, cyclically shifted twice, equal their reverse

Let the alphabet be $Σ = \{0, 1\}$. For any string $w ∈ Σ^*$ of length at least 2, define the operation $C_2(w)$ to be a cyclic shift of size 2 on $w$. That is, if $w = w_1w_2 \cdots w_n$ with $n ≥ 2$ ...
3
votes
1answer
107 views

Regular expression vs rational expression

Let $M$ be a monoid (e.g. $M = \Sigma^*$) and $L \subseteq M$. Then $\mathsf{RAT}(M)$ is the set of rational sets of $M$ and the elements of $\mathsf{RAT}(M)$ are inductively defined as follows: $|L| ...
1
vote
1answer
94 views

Regular language where syntactic right congruence and syntactic congruence differ

Find an example of a regular language where the syntactic right congruence and the syntactic congruence are not identical. I have gone through the relevant definitions and understand them, but could ...
1
vote
1answer
79 views

If we say L ⊂ {a, b, c}* then is L an infinite language?

I wonder if we say L ⊂ {a, b, c}* then is L an infinite language? I think Kleene star makes me think L is an infinite language.
1
vote
1answer
117 views

Constructing a context-free grammar

I want to design a context-free grammar that generates words that either both start and end with $c$, or contain the same amount of $a$-s and $b$-s. Here is what I have. The nonterminals are $S,X,Y$, ...
0
votes
1answer
49 views

Undecidability and Unrecognizability of Language with two Turing Machines

I've been working on undecidability proofs and I found this question in the practice problems for the textbook "An Introduction to Automata Theory." I know that we start by contradicting the ...
-2
votes
2answers
66 views

Prove that the language Cats-Vs-Dogs is undecidable

Define Σ = {a, b, c, . . . , z} be the set of letters in the English alphabet. Prove that the following language is undecidable: Cats-VS-Dogs = {(M) | Either “cats” ∈ L(M) or “dogs” ∈ L(M), but not ...
0
votes
0answers
23 views

Formal languages. What is the definition of $L^*L^*$? [duplicate]

I need to use it to prove $L^*=L^*L^*$. So I know that $L^*=L^1 \cup L^2 \cup L^3\cup\ldots$ But how do you describe $L^* L^*$?
0
votes
1answer
37 views

Regular set of the "does not contain" kind

Given a language $L$ and a set of strings $\Sigma^* = \{0, 1\}^*$, how can I find a regular set that expresses $L = \{ w \in \Sigma^* \mid w$ ends with $00$ and does not contain $11\}$? Well, the part ...
1
vote
1answer
234 views

How to prove the language of contractible strings is context-free but not regular?

How to prove this language is context-free but not regular? I can't figure out it. A string is contractible if there is a sequence of contractions which result in the empty string, where a ...
1
vote
2answers
91 views

Pumping lemma for regular languages. Proof

Please help me understand the following $L = \{ a | a ∈ \{0, 1\}^∗, |a| = k ≥ 4, a = a_1a_2...a_{k−1}a_k, ∃i ∈ N, 1 ≤ i < k : a_i = a_{i+1} \}$ To prove: The language $L$ has regular pumping ...
1
vote
2answers
80 views

Understanding the definition of a language

Could you please help me understand the following Language $L = \{ a | a ∈ \{0, 1\}^∗, |a| = k ≥ 4, a = a_1a_2...a_{k−1}a_k, ∃i ∈ N, 1 ≤ i < k : a_i = a_{i+1} \}$ what does $a_i = a_{i+1}$ mean? ...
0
votes
2answers
78 views

How to prove that $L^* = L^*L^*$

I need to prove or disprove that $L^* = L^*L^*$. Intuitively, I know this is true, and I know I need to prove that $L^*$ is subset of $L^*L^*$ and that $L^*L^*$ is a subset of $L^*$. But I am really ...
1
vote
1answer
187 views

Regular languages closed under prefix operation

Suppose that $D$ is a regular language over an alphabet $A$. How can I prove that the following language is also regular? $$ \mathrm{LANGUAGE}_2(D) := \{ d \mid d,t \in A^* \text{ and } dt \in D \} $$ ...
0
votes
0answers
17 views

L= ${ a^mb^nc^pd^q: m+n<>p+q }$ context free? [duplicate]

I cant find the grammar to prove it is context free but. I also tried a PDA but couldnt make it. Can someone suggest a grammar for this?
0
votes
1answer
106 views

Which of the following words is in the language of the grammar G?

This is taken from a practice quiz by my university. I ruled out that aabbbaab is not part of the grammar: S → aSb → aaSbb... This shows that I can't make this word because it would have to have ...
0
votes
1answer
87 views

Pumping Lemma Proof (Type of wcw language)

I have the language $L = \{ dkd\space \mid d \in \{a,b\}^*, k \in \{a,b\} \}$ and i have to show that it's non-regular using the pumping lemma. The structure of the language i think can be explained ...
1
vote
2answers
70 views

How to evaluate a Kleene's Closure through CFG and attribute grammars

For a CFG with the production rules that can represent a regular expression. How can one calculate all the set of strings that regular expression would produce. For T = {a, b,*,(,)} and an arbitrary ...
0
votes
1answer
64 views

How can I make the following grammar unambiguous

Given the below ambiguous grammar how can I make it inambiguous and how can I prove the new modified unambiguous grammar is unambiguous? S -> S + S | S − S | S ∗ S | S / S | (S) | x | y My attempt: ...
0
votes
2answers
155 views

Cardinality of sets and strings -> confused

I have a question regarding the cardinality of sets and strings. If $ \Sigma^* $ is empty, the cardinality is 1, because the empty word $ \varepsilon $ is counted. If $ \Sigma^+ $ is empty, the ...
3
votes
0answers
62 views

Words of the same length in a language

Let $L\subseteq\Sigma^*$ be a language, where $\Sigma$ is a set, and let $n\in\mathbb N$. I am wondering if there is some good terminology for $L\cap\Sigma^n$. Of course I could say "the set of ...
2
votes
1answer
45 views

Show that moving one symbol to the end still makes a regular language

Question For any string $\sigma$ over alphabet $\Sigma$, we define the operation $\texttt{MOVE}$ as following For $\sigma = aw$ ($a \in \Sigma, w\in \Sigma^*$), $\texttt{MOVE}(\sigma)=wa$ This is ...
-1
votes
1answer
71 views

For every Non Deterministic polynomial Turing Machine $M$ exists $L(\overline{M})\in P \Leftrightarrow P=NP$

The $\Leftarrow$ direction is straightforward. On the other hand for $\Rightarrow$ direction I have an idea of the prove but I don't sure about it. For NTM, Non Deterministic Turing Machine, $M$, for ...
0
votes
1answer
28 views

Is there a non-deterministic polynomial by time Turing machine such that: $L(M)\in NPC$ and $L(\overline{M})\in P$

When $\overline{M}$ is a non-deterministic polynomial by time Turing machine that final states switched: accept to reject and vice versa. I'm thinking that this equal to $P=NP$, but I saw a solution (...
0
votes
2answers
65 views

Show $\{0^𝑚1^𝑛|𝑚≠𝑛\}$ is not regular

So I have the question: show "Show $\{0^𝑚1^𝑛|𝑚≠𝑛\}$ is not regular". I've already seen various proofs for this question, but they all have one step I don't get. They all take: $\bar{L}∩(...
1
vote
1answer
73 views

Proving that $ \{u\#v\#w \mid u,v,w \in {a,b,c}*, |u|_a = |v|_b = |w|_c\}$ isn't context-free

I have a question about the pumping lemma for context-free languages. I understand the conditions of the pumping lemma. Assume $L$ is context-free. Let $n>0$ be the pumping length given by the ...
1
vote
1answer
40 views

A question about domains in Karp reductions

A basic question or request for clarification regarding Karp reducibility: Let $\Sigma^*$ be the set of all finite strings of 0's and 1's. Call a subset of $\Sigma^*$ a language. Let $\Pi$ denote ...
0
votes
1answer
35 views

Formal Grammar: derivation form posted on Wiki?

Wiki describes the binary relation $\underset{\mbox{G}}{\implies}$ as "G derives in one step". I have a question on the condition when there are multiple productions for a single non-...
0
votes
0answers
19 views

generating strings from this formal grammar [duplicate]

Hey guys I am having trouble generating strings from this language, I haven't seen a grammar that looks like this and can't figure how to generate strings from this grammar, is this Context Sensitive ...
1
vote
2answers
123 views

Prove that $(L^R)^* = (L^*)^R$

Prove that $(L^R)^* = (L^*)^R$ for all languages $L$. My attempt: Suppose $w \in (L^R)^*$. So, $w = w_1\dots w_l$, for some $w_1, \dots , w_l \in L^R$. Since $w^R \in L$, then $w^R = w_l\dots w_1$, ...
1
vote
2answers
205 views

Show that $L$ and $\overline L$ cannot be both finite

Let $L$ be any language on a nonempty alphabet. Show that $L$ and $\overline L$ cannot be both finite. This is exercise 7 (page 28) from "An Introduction to Formal Languages and Automata" ...
0
votes
1answer
154 views

Let $\Sigma = \{a, b\}$ and $L = \{aa, bb\}$. Use set notation to describe $\overline L$

Let $\Sigma = \{a, b\}$ and $L = \{aa, bb\}$. Use set notation to describe $\overline L$. This is exercise 6 (page 28) from "An Introduction to Formal Languages and Automata" by Peter Linz. ...
1
vote
1answer
295 views

Prove that $(uv)^R = v^Ru^R$

The reverse of a string, introduced informally above, can be defined more precisely by the recursive rules $$a^R=a,$$ $$(wa)^R=aw^R,$$ for all $a \in \Sigma$, $w \in \Sigma^*$. Use this to prove that $...
2
votes
2answers
86 views

Why can't we compute the lexicographically-least word of a given length on which a given TM halts?

I had this question in my exam. but my answer is wrong(I didn't receive explanations why...) $$f(\langle M\rangle,1^n)=\left \{ \texttt{the lexicographically smallest } x\in\left \{ 0,1 \right \}^n \...
1
vote
1answer
62 views

Why every finite language is polynomial?

I understand that it's possible to build TM that check all the finite number of cases, so it's definitely in $R$, but I'm not sure why it's in $P$
-3
votes
1answer
47 views

Proof of existence of $L\in R\setminus P$

I saw some proof but I didn't understood it, any simple one?
2
votes
1answer
47 views

Proof that $L = \{a, b\}^* - \{(a^n b^n)^m \mid n, m \ge 1\}$ is a CFL

I want to prove that $L = \{a, b\}^* - \{(a^n b^n)^m \mid n, m \ge 1\}$ is a Context Free Language. so far, I tried to find a Context Free Grammar for $L$ or to use properties of Context Free ...
0
votes
1answer
64 views

$L_{\Sigma^*}=\{\langle M\rangle|L(M)=\Sigma^*\}\notin coRE$

I'm trying to understand why: $$L_{\Sigma^*}=\{\langle M\rangle|L(M)=\Sigma^*\}\notin coRE$$ As I see it TM, $\langle M\rangle$, should accept all the inputs, and if one of the inputs rejected it's ...
1
vote
1answer
35 views

Difference between $ L_1 = \{(a^n b^n)^m \mid n, m \ge 1\} $ and $ L_2 = \{a^n b^n \mid n \ge 1\}^+ $

Is there any difference between saying $ L_1 = \{(a^n b^n)^m \mid n, m \ge 1\} $ with $ L_2 = \{a^n b^n \mid n \ge 1\}^+ $? I know that for $v = abab$ we have $v \in L_1$ and $v \in L_2$ my ...
0
votes
0answers
21 views

I am trying to design an LL(1) Parser that accepts T = {a, b *, +, ?, E, U, (, ) }

I am trying to design an LL(1) Parser that accepts regular notation where 'E' represents epsilon, and 'U' represents "or" like ' | '. So far I made one that accepts T = { a, b, *, +, (, ), E}...
2
votes
0answers
25 views

Why process algebras à la chemical abstract machine are not common?

I recently read the Berry and Boudol's chemical abstract machine [1, 2]. I found the way they describe the semantic really nice and quite intuitive for a process calculus. The aspect that really ...
1
vote
1answer
49 views

Using closure properties, prove that $L=\{a^kb^ra^m|k,r,m\ge0 \text{ and } m=k+r\}$ is not regular

I'm trying to prove that $L=\{a^kb^ra^m|k,r,m\ge0 \text{ and } m=k+r\}$ is not regular and, although it's trivial to prove it via pumping lemma, I'm having troubles trying to find a way to prove it ...
0
votes
1answer
57 views

Computing $(a+b)^*c^*(a+b)^* \cap (b+c)^*a^*(b+c)^*$

how can I find the regular expression for this intersection ? I've tried to find words but it did not help too much.. $$[\; (a+b)^* c^* (a+b)^* \;] \cap [\; (c+b)^* a^* (c+b)^*\;]$$
0
votes
1answer
59 views

Complementary for $SAT$

I have tried to find a definition of complementary language to $SAT$, I mean $\overline{SAT}$. But I still confused, in case of $L\in \overline{SAT}$ is it mean: if $\varphi\in L$ then all ...
3
votes
2answers
90 views

Context free grammar for $L = \{w \text{ | }w \in \{a,b\}^*, |w|_a=|w|_b-1\}$

I'm trying to find a grammar for $L = \{w \text{ | }w \in \{a,b\}^*, |w|_a=|w|_b-1\}$, which is proving to be tricky. I know that $L_2 = \{w \text{ | }w \in \{a,b\}^*, |w|_a=|w|_b\}$ has the following ...
2
votes
1answer
112 views

Formal Binary String Regular Expression (each pair of 00 must have 11 before it)

I'm trying to construct a regular expression for the language of binary strings in which every 00 must have at least two 1s before it. I realize this can be done with lookbehinds using the following ...
-1
votes
2answers
75 views

Recursively enumerable notation $RE$ vs. $RE\setminus R$

I know that it's a bit stupid question.. , but still, Is there any difference between $RE$ and $RE\setminus R$ notations? I'm asking because I saw that in some places using both of the notations, for ...

1 2 3
4
5
52