Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

Filter by
Sorted by
Tagged with
0
votes
1answer
48 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
39 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
48 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
62 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
42 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
35 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
105 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
66 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
37 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
106 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
33 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$ ...
0
votes
1answer
29 views

Some questions regarding decidability and semi-decidability of $A/B = \{ w \text{ | }\exists z \in B, wz \in A\}$

I have found two interesting questions regarding the quotient of languages, described as: $A/B = \{ w \text{ | }\exists z \in B, wz \in A\}$ The first one is: Let $A$ and $B$ be regular languages, ...
0
votes
0answers
15 views

Regular expression for all words not containing 222 [duplicate]

I need to find a regular expression for the language of all words over $\{0,1,2,3\}$ which do not contain $222$ as a substring.
6
votes
5answers
3k views

I'm trying to understand why every language has an infinite number of TMs that accept it

I found the following answer: $L_{17} = \{ \langle M \rangle \mid \text{$M$ is a TM, and $M$ is the only TM that accepts $L(M)$} \}$. R. This is the empty set, since every language has an infinite ...
1
vote
1answer
70 views

Number of sentences and sentential forms generated by a grammar

In this question, I'm considering only "finite grammars". A finite grammar can only produce a finite number of distinct sentences. The following grammar is finite in my definition: ...
1
vote
1answer
36 views

Some questions regarding methods for solving pushdown automata problems

I have found some problems whose solving "patterns" appear quite recently, and I am not sure if the way I'm solving them is the most correct/efficient one: For example, take this language: $\...
0
votes
1answer
26 views

Is the complement of the language generated by $S \to aSbS|\epsilon$ context-free?

How is it possible to prove whether the language $\{a, b\}^{∗} \setminus \{S → ε, S → aSbS\}$ is context free?
0
votes
0answers
26 views

How to proof that this ratio isn't the finite transformation?

How to check if the ratio is given: $a^{m}b^{n}a^n \rightarrow a^{m}b^{n}a^{m}$ by finite transformations? I tried using the pumping lemma for finite transducers, but that didn't get me anywhere. ...
0
votes
0answers
46 views

Finite state transducer that multiplies numbers

How is possible to construct a finite state transducer that multiplies a number by 5? We can assume that numbers are supplied in binary notation, from least significant bits to most significant.
1
vote
1answer
54 views

Write a CFG for the language $\{0^n 1^a 2^b \mid n = a+b\}$

I would like some help for the computation theory. There is a PDA that accepts the language $\{0^n 1^a 2^b \mid n = a+b\}$, so how can I express it into context free grammar? Any help would be ...
1
vote
1answer
39 views

What is the language of Sigma^n? Confused about meanining

I am learning the Theory of Computation, and I came across the language $\Sigma^n$. Could someone please explain what that could mean if $\Sigma$ is the alphabet? Thank you so much!
1
vote
1answer
32 views

Finding right quotient of $a^*b^*/b^*.$

I argue that right quotient of $a^*b^*/b^*$ is $a^*$,is that true?any help or argument to accept or reject my argument will be appreciated:)
0
votes
0answers
20 views

What's the union between a decision problem and its complement

I see the union of problems as something like this: $P=F\cup G$ $P(\omega):$ $\;\;\;\;if\; F(\omega)==True: return \;\; True$ $\;\;\;\;else\;if\; G(\omega)==True: return \;\; True$ $\;\;\;\;else: ...
0
votes
0answers
47 views

How can I show that the function f(u, v) = uv is computable in programming language S_n. Here uv is concatenation of the words u and v

This is in reference to a question I found in chapter 5 (Calculation on strings) Computability, Complexity, and Language by Martin D. Davis
2
votes
1answer
85 views

Minimal DFA accepting strings whose length is divisible by $x$ or $y$

Consider the language of all strings whose length is divisible by either $x$ or $y$, where $x,y \geq 1$. After trying various values of $x$ and $y$, I noticed made the following observation: If one ...
0
votes
0answers
501 views

Turing machine that recognizes the language $\{a^{n}b^{2n}c^{3n}|\ n\ge0\}$

I'm pretty sure that the Turing machine state diagram I drew accepts all strings in the language $\{a^{n}b^{2n}c^{3n}|\ n\ge0\}$, but how do you verify this? Likewise, how do you verify that this ...
0
votes
3answers
144 views

Difference between a regular and a non-regular language

Suppose $L_1$ is a regular language and $L_2$ a non-regular one, then: is $L_1\setminus L_2$ REGULAR/NON REGULAR/BOTH OF THEM? is $L_2\setminus L_1$ REGULAR/NON REGULAR/BOTH OF THEM?
0
votes
2answers
233 views

Is $L = \{ a^ib^j : 0 < j < i < 2j\}$ context free? How can it be shown?

Is $L = \{ a^ib^j : 0 < j < i < 2j\}$ context free? If so, can there be a pushdown automaton described for it? If not, does the pumping lemma apply?
0
votes
0answers
37 views

What kind of automaton recognizes closed terms of the lambda calculus?

There seems to be an interesting model of computation involved in determining whether a term from some programming language has any free variables. It's a tree traversal that seems almost like the ...
0
votes
1answer
42 views

Can PDA accept only by final state without finish reading input?

I am defining, a string $w$ is accepted by a PDA whenever the PDA enter into a final state during the computation(at least on one branch of the computation) on the input $w$ (no matter whether the ...
0
votes
1answer
53 views

Myhill-Nerode classes for a Language $L_k = \{x1y | x \in \{0, 1\}^*, y \in \{0, 1\}^{k-1}\}$

This problem is from an exercise sheet so it would be nice if you could guide me to the solution. The problem: For $ k \in \mathbb{N}\setminus\{0\}$ let $$L_k = \{x1y | x \in \{0, 1\}^*, y \in \{0, 1\}...
-1
votes
1answer
36 views

Prove that the class of regular languages is closed under the Kleene + operation. That is, show that if L is regular, then so is $L^{+}$

This is my attempt at a proof: Let $E$ be a $REGEX$ accepting $L$. We claim the $REGEX$ $E^{'} = E^{+}$ accepts L. i.e. $L(E^{+}) = (L(E))^{+}$ $L^{+}$ is regular since there is a $REGEX$ $E^{+}$ ...
0
votes
1answer
40 views

Generate the context free grammar for the following language: $\left \{ a^{3n}b^{m}c^{n}|n>0, m>0\right \}$

Given the following language, I am tasked with giving a context-free grammar that generates it. $\left \{ a^{3n}b^{m}c^{n}|n>0, m>0\right \}$ Would this be correct? $A \rightarrow aaaA$ $B\...
0
votes
1answer
65 views

Create a Deterministic Finite Automaton for a regular expression

I want to create a finite state machine that accepts the following language: $$ L=\{w\in\{a,b\}^* | w \text{ contains abb but not on the first position}\} $$ So I began by writing a regular expression ...
0
votes
0answers
28 views

Parsing a context free grammar, Backus Naur question

Does anyone know how BNF rules expecting the empty string ($\epsilon$ or the "") behave during creation of a parse tree using grammar from a string of ...
1
vote
2answers
84 views

Proving some subsets of a regular languages to be regular languages

I have to prove that if a language $L$ is regular then: a) $NONPREFIX(L)=\{u \in L / $none of the prefixes (not $\epsilon$ or $u$) of $u$ are elements of $L \} $ is regular On this one I think I can ...
2
votes
2answers
59 views

Irregularity of $\{0^x1^y : y \nmid x\}$

The language $L=\{W\in\{0,1\}^{*} \mid W=0^{x}1^{y} \text{ where } x\geq0, y>0 \text{ are integers and } y\nmid x\}$ is not regular. How would one prove this using Pumping Lemma? I thought about it ...
1
vote
1answer
960 views

What does it mean for a grammar to be LR(0)?

I am unsure what it means for a grammar to be $X$. More specifically, what it means for a grammar to be LR(0). For part of an assignment I had to form the DFA for a grammar, which I had no issues with....
2
votes
1answer
77 views

How can I show that this language is context sensitive?

I have this language $L=\{a^nb^nc^n,n\geq0\}$, I know this language is not context free, but I don't know how to show that it is context sensitive, do I have to use a PDA?
2
votes
1answer
79 views

What are the most used statements in programming (ranked)?

I was wondering if there are any resources for a study/ranking of the most frequently used statements (by statements I mean assigning, invoking, instantiating etc, like in C#) in programming overall (...
1
vote
0answers
57 views

How to prove a statement in regular expression?

I cannot figure out how to go about proving this statement in regular expression. $$ L(R_1) \subseteq L(R_2) \subseteq L(R_3) \implies L(R_1^*+R_3)^* \subseteq L(R_2^*+R_3^*) $$ Here's what I have ...
0
votes
1answer
42 views

Formal proof of language accepted by a specific CFG

Let $G=(V,\Sigma,R,S)$ be the grammar given by the following rules: \begin{align} &S \to aS \mid B \\ &B \to abBc \mid \epsilon \end{align} Please provide a formal proof for the following ...
0
votes
1answer
100 views

Proving the language of non-primes is in NP

I am learning about NP problems and found this problem in my textbook that I was not sure how to answer, and was looking for some help on how to start the question. Show the following language is in ...
0
votes
0answers
14 views

Having trouble understanding how to prove a language context free? [duplicate]

I've been studying the theory of automata. I came across this problem in the book and unable to understand how to solve this. I've solved some examples using the Pumping lemma but this one uses ...
0
votes
0answers
39 views

How did we go from Binary to something like Python?

If there's one thing the pandemic has shown us its that High school Geometry did not save us. I am a high school math teacher and I understand my job and its usefulness only exist in a post scarcity ...
0
votes
1answer
61 views

If two languages are decidable, can one be mapping reducible to the other?

If I have two decidable languages $A$ and $B$, is $A \leq_m B$ true? How would I show this?
0
votes
0answers
52 views

When are existential quantifiers in the intuitionistic propositional calculus eliminable and when not

I am so ignorant I don't even know where should I ask this - on FOM? On mathoverflow? On cstheory? So please consider as sort of a meta-question readdressing me in case you think this is a wrong site. ...
5
votes
4answers
589 views

Is there a formal definition of sub-instances or sub-problems?

A decision problem is denoted as a language $L \subseteq \Sigma^{*}$. For every instance $x \in \Sigma^{*}$, we say $x$ is a yes-instance if $x \in L$ and a no-instance if $x \not\in L$. For some ...
0
votes
1answer
40 views

Is this an unambiguous CFG that is not LR(k) for any k?

The grammar is this: $$S \rightarrow a B c $$ $$B \rightarrow b B b $$ $$B \rightarrow \epsilon $$ The LR(1) states that I worked out were these $$(1)$$ $$S \rightarrow .aBc$$ $\\\\$ $$(2)$$ $$S \...
0
votes
0answers
37 views

Check if given safety properties are regular, and if so construct NFAs

Let $\mathit{AP} = \{a, b, c\}$. Consider the following LT properties: Between two neighboring occurrences of $a$, $b$ always holds. Between two neighboring occurrences of $a$, $b$ occurs more often ...

1 2 3
4
5
51