Questions tagged [formal-languages]
Questions related to formal languages, grammars, and automata theory
2,432
questions
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$ ...
