Questions tagged [formal-languages]
Questions related to formal languages, grammars, and automata theory
2,574
questions
3
votes
1answer
134 views
0
votes
1answer
33 views
Proving undecidability of a language with mapping reductions
I'm referring to questions like this one:
Mapping reduction to show NeverHalt is undecidable
I understand with Turing reductions, you have to use oracle calls of the unknown language you're trying to ...
0
votes
0answers
27 views
If $L_1 \leq_m L_2$, and $L_2$ is decidable, is $L_1$ then decidable?
There is a lemma in our textbook that asks us to prove the following:
If $L_1 \leq_m L_2$, and $L_2$ is decidable, then $L_1$ is decidable
I tried proving this by saying that if $L_1 \leq_m L_2$, ...
1
vote
1answer
16 views
DFA and a Partition of $\Sigma^*$
So I'm learning about Myhill-Nerode relations and as an introduction, the book describes possible partitions for $\Sigma^*$. As an example, given a language $L$, a partition of $\Sigma^*$ would be $\{...
0
votes
0answers
20 views
How to count the number of nodes for a tree generated by context free grammar derivation?
Given context free grammar I use breadth first search and left most derivation rule to generate all possible words for a given language.
For example:
...
0
votes
0answers
15 views
A regular expression E* defines an infinite language $L_E$ [closed]
So I'm studying for an exam which is about languages and automata. There is a question in the book which asks us to prove that given a regular expression that can be infinite, say $E*$, the language ...
-1
votes
0answers
17 views
Describe how to build a non-deterministic Turing machine that accepts the set of all element prefixes of $L$, i.e, $PREFIX(L)$
Describe how to build a non-deterministic Turing machine that accepts the set of all element prefixes of $L$, i.e, $PREFIX(L)$.
Hello, I have been trying to solve this problem, my intuition tells that ...
-2
votes
0answers
28 views
Prove by reduction that the language $L^♦ = \{N | N \text{ is a } TM \text{ and } L(N) \text{ is a recursive language}\}$ is not recursive
Prove by reduction that the language $L^♦ = \{N | N \text{ is a } TM \text{ and } L(N) \text{ is a recursive language}\}$ is not recursive.
Hi, I've been strugling with this problem since yesterday, ...
1
vote
1answer
36 views
Disambiguating grammar for Dyck language
Given the following simple grammar for a language that contains all strings with matched parentheses:
\begin{align}
&s \to ss \\
&s \to (s) \\
&s \to ()
\end{align}
Examples: $(), ()(), (()...
1
vote
1answer
35 views
Find a transducer that maps a given deterministic process to another
Let $S$ denote a deterministic process which generates a certain string, described through a Hidden Markov Model. More specifically, for a process with alphabet $\mathcal{A}$ and $n$ hidden states, ...
-3
votes
0answers
26 views
CFLs are accepted by two-state PDAs w/o $\epsilon$-transitions
Show that if $L$ is accepted by a PDA, then $L$ is accepted by a PDA having at most two states
and no $\epsilon$-transitions.
1
vote
1answer
99 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
1answer
34 views
kolmogorov complexity for finite Language?
In lectures my professor proved that there is no Turing machine that for every x it calculates k(x).
On the other hand, I saw a claim online that for finite language L there is a Turing machine that ...
1
vote
1answer
43 views
Understanding the application of the pumping lemma to show that $L=\{0^{2^p}, p \geq 0\}$ is not regular
I want to understand how is this proof working.
What I know:
Pumping lemma for regular language-:
Let $L$ be regular language. Then there exists a constant $n$ which depends on $L$ such that for every ...
0
votes
1answer
166 views
How to design a formal grammar to convert EBNF description to a list of CFG production rules
I would like to write a grammar to convert EBNF description to a list of CFG production rules, instead of an algorithm.
Can CFG production rules is generated from an EBNF description by a rewrite ...
0
votes
3answers
65 views
Making a simplest possible CFG to recognize the language L = {a^i b^j c^k | i + j ≥ 2k}
The language given is $L = \{a^i b^j c^k\mid i+j \ge 2k\}$ for which I need to construct a simplest possible Context Free Grammar.
I tried understanding but I could only go as far as making sense of $...
1
vote
2answers
48 views
Are there any algorithms that decide if a PDA (pushdown automaton) accepts a sentence?
Most computation theory textbooks just mention the equivalence of PDAs and Context Free Grammars. I'm able to construct a PDA from a given CFG, but find it very difficult to write an algo to check if ...
28
votes
2answers
38k views
How to prove that a language is context-free?
There are many techniques to prove that a language is not context-free, but how do I prove that a language is context-free?
What techniques are there to prove this? Obviously, one way is to exhibit ...
0
votes
0answers
42 views
Construct PDA for $\{a^ib^j\ | i > j \ \& \ i < 2j\}$ [duplicate]
How to construct PDA for language $\{a^ib^j\ | i > j \ \& \ i < 2j\}$?
I know how to check first and second conditions separately but at once there's a problem.
6
votes
2answers
2k views
Why is $\emptyset L = L\emptyset = \emptyset$ correct?
I am taking a course on Automaton where I faced the algebraic laws of regular expressions.
First two were ok:
$\emptyset + L = L + \emptyset = L$: Union of a language $L$ with empty language gives ...
1
vote
1answer
36 views
Is there a way to show that if the description of a language depends on some kind of global structure, then it isn't a CFL?
So I've been reading Sipser's theory of computation book, and I've come across the pumping lemma for context-free languages, which as a reminder says that if a language is context-free, then there is ...
0
votes
2answers
776 views
turing machine for the language L ={w#w' where w<w'}
I'm blocked with a question for a long time.
L ={X=w#w' where w < w' and w,w' in {0,1}* }
So i'm trying to find :
1-a deterministric turing maching for the language L.
2-a non deterministic for ...
2
votes
1answer
223 views
Brzozowki's algorithm doesn't work for this corner case
I'm a newbee learning DFA minimization. And I found that(strangely) Brzozowki's algorithm cannot give me a minimized DFA on this example:
In this DFA, $S_0$ and $S_1$ are nondistinguishable and ...
0
votes
1answer
132 views
Context free grammar for $1^n 0^m 1^k 0^p$ where $n+k=m+p$
i need to convert this CFL to CFG
$$ L = \{\; 1^n 0^m 1^k 0^p \mid n\ge 2, k,m,p\ge 1, n+k=m+p\;\} $$
I am trying to solve this problem for a few days but i couldn't. Is there anyone to help me? I'm ...
0
votes
1answer
56 views
Size of minimal DFA
Assume a given NFA for a regular language with $n$ states. It is clear that determinizing it may result in an DFA with $\Omega(2^n)$ states. However, the minimization might decrease the number of ...
1
vote
1answer
32 views
A turing machine L takes a machine <M> which has to halt at for least n Inputs
I've been wondering about this problem for a while:
Say we have L = { <M>, n | M has to halt for at least n Inputs}
and multitapes are simulating various inputs bla bla
How do I count how many ...
1
vote
2answers
36 views
We cannot recognize a set of languages as the language themselves
"We cannot recognize a set of languages as the language themselves"
What is the meaning of the line and why we cannot do it and how is the encoding of TM is helping in that?
0
votes
1answer
57 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 ...
-1
votes
1answer
561 views
How to define a language for an independent set problem of a graph?
Let a graph $G=(V,E)$ have an independent set $I\subseteq V$ with $\{u,v\}\notin E$ for all $u,v \in I$ and $k \in \mathbb{Z}_{>0}$ where $|I|=k$.
How can I define the language $L_{P_{Independent ...
0
votes
0answers
39 views
Complement of a context free language
Consider the context-free language of balanced parentheses of three kinds:
$$L = \{w \in \{ (, ), [,], \{, \} \}^∗ \mid \text{all parentheses in }w \text{ are properly balanced}\} $$
What will be the ...
0
votes
2answers
77 views
Show that $\{xy : x \in \{a\}^*, y \in \{b\}^*, |x| = |y|\}$ is a not a regular language
I have been asked as an exercise how to prove that this is not a regular language. first I tried to use the pumping lemma, but I got stucked. Th erxercise hust said to prove thata this isn't a regular ...
-1
votes
1answer
19 views
Is a one step derivation grammar context free?
Suppose we have a grammar having a one step derivation like
S -> a
where 'S' is a variable and 'a' is a terminal.
Since this grammar does not pump terminals, can we say that the language generated ...
0
votes
0answers
16 views
Find CFG for bin(n)bin(2n+3)^R
Where bin(n) is the shortest binary representation of n.
First, we can see that we can rewrite it as $bin(n)bin(2(n+1)+1)^R$ which implies that the second word will always start from 1.
We can also ...
0
votes
0answers
57 views
Construct CFG of monadic logic
How to construct CFG for tautologies in monadic predicate logic in the empty model. The predicates are Q and P, operations are ...
2
votes
1answer
2k views
How would a Turing Machine recognize n consecutive characters
I have difficulties understanding how a TM could count number of characters. I have this problem where the input is made out of characters $\{a, b\}$ and I need to accept if there are $n$ characters ...
1
vote
1answer
35 views
Proving irregularity of $a^{k!}$ using Nerode's theorem
Use Nerode's theorem to prove that the following language $L$ is not regular:
$$ L=\{a^{k!} \mid 1\leq k\} $$
Here is my attempt:
Let $A$ be an infinte set of words s.t- $$ A=\{a^n \mid n\in \mathbb{...
1
vote
0answers
19 views
How does one parse a string into an AST (Abstract Syntax Tree) directly instead of to a CST (Concrete Syntax Tree)?
I wanted to parse strings to AST data structures instead of CSTs - which introduce a lot of intermediate nodes like terminal that might not be needed. I am not sure if one first creates a CST and then ...
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 ...
0
votes
0answers
26 views
PDAs with bounded stacks accept regular languages [duplicate]
I've been trying to solve the following problem from Martin's Introduction to languages and the theory of computation, 4th edition:
Suppose that $L \subset \Sigma^{*}$ is accepted by a PDA $M$. ...
1
vote
2answers
58 views
For $L_S=\{\langle M\rangle : L(M)\in S \}$ what know about $S$ if
For $L_S=\{\langle M\rangle : L(M)\in S \}$ what know about $S$ in case of:
$L_S\in RE$
$L_S\in R$
3
votes
4answers
70 views
Star notation for context-free language alphabet?
I noticed that some "design-the-grammar" problems say verbally
Alphabet is $\mathbf{\{0,1\}}$.
$\{w \mid w \text{ contains at least three 1s}\}$
and some problems list it as
$\{ w ∈ \...
-1
votes
1answer
47 views
Is the right quotient of a regular language respect to another regular language a regular language?
Will the language $\{w\in L_1\mid \exists v, wv\in L_2\}$ be regular if $L_1$ and $L_2$ regular languages?
0
votes
1answer
24 views
DPDA by empty stack
Let's say we have DPDA with acceptance by empty stack, w is accepted by this DPDA. Why can't wv be accepted? I know about the prefix property but i don't see where it's coming from. Can't we just ...
1
vote
3answers
324 views
Need help understanding what co-recursively enumerable means
Lets say I have a set: $ L = \{\langle G \rangle | L(G) = \Sigma^{\star}\}$ and the question asks if it is co-RE. I know that if something is co-RE, it halts on every input not in L but may or may not ...
0
votes
0answers
21 views
How to prove that this "priority" strategy (in ANTLR4) solves the "dangling-else" ambiguity?
As shown in this post @ stackoverflow, ANTLR4 seems able to resolve the "dangling-else" ambiguity @ wiki in the following "if-then-else" grammar by prioritizing the "...
0
votes
0answers
24 views
Turing Machine that accepts L(M1) = {x^n y^2n z^n | n ∈ N}
I'm trying to design a Turing machine that accepts all strings in the language $$\{x^{n}y^{2n}z^{n}|\ n\in N\}$$ but I'm having trouble getting it to accepts when n> 1, for some reason it rejects ...
0
votes
3answers
238 views
How it's possible decide CNF by having a turing machine that decide SAT?
Suppose we have a Turing machine $M$ as black box that decide $SAT$ problem. Now suppse we have a $CNF$ formula $\phi$ with $n$ variables. How it possible checking satisfiblity of $\phi$ and then ...
0
votes
1answer
97 views
Determining recursive enumerability of given languages
I came across following problem:
$L=\{M$ is a turing machine $M$ accepts two strings of different length $\}$
$L=\{M$ is a turing machine $M$ accepts atleast two strings of different length $\}...
0
votes
0answers
19 views
Is there any problems with equating Turing Machines with Algorithms and Language with Problems?
In a lot of the online explanation of complexity theory, the author proposes the following.
"The definition associated with complexity theory (e.g., definition of
NP) is phrased in terms of ...
47
votes
2answers
8k views
What is the difference between an algorithm, a language and a problem?
It seems that on this site, people will often correct others for confusing "algorithms" and "problems." What are the difference between these? How do I know when I should be considering algorithms and ...
