Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

Filter by
Sorted by
Tagged with
0
votes
1answer
36 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
48 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 ...
0
votes
2answers
27 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
44 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
46 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 ...
2
votes
0answers
50 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 ...
-4
votes
0answers
31 views

Prove that $f(L)=L_{\Sigma^*}$

When: $f(L)=\{f(x) | x\in L\}, L\in R$ $L_{\Sigma^*} = \{\langle M\rangle | L(M)=\Sigma^* \}\notin RE$ and $\langle M_{\Sigma^*}\rangle$ is TM that accept straight away. For: $f(\langle M\rangle)=\...
2
votes
1answer
26 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 ...
-2
votes
0answers
44 views

$\forall A\notin RE$ prove that $L_A =\{\langle M\rangle : |A\cap L(M)|\ge10 \}\notin RE $

My solution for this question is: Reduction from $L_A$ to $A$, in the following way $f(x)=\langle M_x\rangle$ Emphasis: $\exists$ 10 different words $w_1 ,\dots,w_{10}\in A$, otherwise $A$ finite $\...
-1
votes
1answer
63 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
23 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
42 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
47 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
0answers
14 views

Language of all words of the form $xwwy$, where $x,w,y \neq \emptyset$ [duplicate]

I have the following question: Determine whether the following language is regular or not, and prove it: $$L = \{xwwy \mid w,x,y ∈ Σ^*,w,x,y \neq ε\}. $$ My idea was that any string with at least 1 ...
1
vote
1answer
33 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
22 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
18 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
1answer
35 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
43 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
44 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
37 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
77 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
34 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$
-4
votes
1answer
40 views

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

I saw some proof but I didn't understood it, any simple one?
-6
votes
0answers
29 views

Modify DFA/NFA that accepts Language [closed]

(a) Make a DFA that accepts all strings that start with ‘ab’, and end with ‘aa’.
2
votes
1answer
43 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
32 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
31 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
20 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}...
1
vote
0answers
17 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
25 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 ...
1
vote
1answer
47 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
51 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
64 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
52 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 ...
-2
votes
2answers
64 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
vote
1answer
36 views

Is there a formal language of Combinatory Logic's expressions?

The Combinatory Logic uses expressions of the form (x y) called "applications" (here, we have an "application of x to y"). Thus, the language of CL is a set of "parenthetic ...
2
votes
0answers
31 views

Subexponential size of string to prove $\{xy : x,y \in \{0,1\}^\star, |x| = |y|, x \ne y\}$ is not regular?

In the standard proof of this language not being regular using the Pumping Lemma for Regular languages, one picks $0^p 1^p 0^{p+p!} 1^p$ where $p$ is the pumping constant and using that can derive the ...
0
votes
1answer
39 views

For s set $S\subseteq RE$, so call feature of language $S=\emptyset$ vs. $S=\{\emptyset\}$

I'm trying to understand what's the difference between $S=\emptyset$ and $S=\{\emptyset\}$ The diffenition that I found for $L_S=\{\langle M\rangle\ | L(M)\in S \}$ I understood that $S=\emptyset$ and ...
0
votes
1answer
47 views

Is a language recursive? 2 wrong ways of solving

Let's define: $Disagree(M_1,M_2) = \{x| $The result of $M_1$ on $x$ different from the result of $M_2$ on $x\}$ that means: if $M_1$ accept, $M_2$ reject and vice versa $NPA=\{L|\exists M_1,M_2$ ...
0
votes
1answer
33 views

If$A \leq_T B$ is given, can you reduce $\overline{A}$ to $B$ and vice-versa

If you are given two languages $A$, $B$ and $$A \leq_T B.$$ Is it possible to $\overline{A} \leq_T B$ or $A \leq_T \overline{B}$? Here is my shot. Case 1: $\overline{A} \leq_T B$ This is only possible ...
2
votes
2answers
36 views

Textbook on formal syntax (and semantics) of programming languages

I'd like to learn about formal syntax of programming languages: how do we describe the syntax of a programming language and how it should be parsed? How do we assign formal semantics to a parsed ...
2
votes
2answers
53 views

State whether the language is in $R$, $RE$, etc. The intuition for the solution

I saw the solution but can't understand the intuition of the following question: Let's define $$L^{\ge k} = \{w\in L : |w| \ge k\}$$ and $$L=\{\langle M\rangle | \exists k:L(M)^{\ge k} = \overline{HP}^...
1
vote
1answer
36 views

Finding a grammar for $L=\{a^nb^mc^rd^s| n+m<r+s\}$

I am trying to find a grammar for $L=\{a^nb^mc^rd^s| n+m<r+s\}$, which has the hint of it having "some similarity" to $L=\{a^ib^j|i<j\}$ This last one is quite easy to get ($S\to aSb | ...
1
vote
1answer
30 views

Finite languages $L\in RE$

I want to check if I understood it in the right way. In some example where $L\in RE$ the explanation deal with 2 cases: 1st when $L$ finite and 2nd when $L$ infinite. In the second case $L\in R$, isn'...
2
votes
4answers
73 views

If $L$ is regular then $L^{|2|}=\{w_1w_2 \mid w_1,w_2\in L, |w_1|=|w_2|\}$ is context-free

I have found a problem about proving whether $L^{|2|}=\{w_1w_2 \mid w_1,w_2\in L, |w_1|=|w_2|\}$ is context-free or not, knowing that $L$ is regular So far I know that: There are examples where $L$ ...
1
vote
2answers
61 views

Finding a grammar for $L = \{ 0^x1^y0^z1^w | x+w=y+z\}$

I have found an exercise where it tasks to provide a grammar and a pushdown automata for $L = \{ 0^x1^y0^z1^w | x+w=y+z\}$ While finding a pushdown automata for it is quite easy (four states and two ...
2
votes
2answers
33 views

If $A \in \mathrm{RE}$ and $A \leq_m \overline{A}$ then $A\in \mathrm{R}$

I found the following question with an answer here, but I can't understand the steps of the solution. Show that if a language $A$ is in RE and $A \leq_m \overline{A}$, then $A$ is recursive. Solution....
0
votes
1answer
35 views

Understanding the union of an undecidable language with a finite or decidable language

I'm trying to prove that the language $L \cup A$ is undecidable, when the language $L$ is undecidable and the language $A$ is finite or decidable. This is confusing me because if $L$ were to be a semi-...
0
votes
1answer
32 views

De morgan's law in formal language

I found in some exercise in computation the following step: I can't understand why is it equal terms, based of what I know about De morgan's law: OR should be replaced by AND where $w=\varepsilon$ ...

1
2 3 4 5
49