Questions tagged [formal-languages]
Questions related to formal languages, grammars, and automata theory
2,150
questions
0
votes
0answers
17 views
Deciding whether CFG generates the empty word
Give an algorithm to decide the following problem: given
a CFG $G$, does $G\Rightarrow^\star \epsilon$? That is, given a grammar can it
generate the empty word? How can I make sure my algorithm is ...
4
votes
1answer
90 views
How to prove the set of powers of 2 in ternary representation to be non-regular using pumping lemma?
Given the set of natural numbers, $S = \{2^i|i\in\mathbb{N}\}$ let $L$ be the language defined as the ternary representation of all numbers in $S$. How can you prove that this is not a regular ...
1
vote
1answer
37 views
Is there any base representation that produces a non-regular language for set S?
To clarify, by base representation I mean binary representation (ie. 101 = 5), ternary representation, etc.
Given the set $S$ of natural numbers such that $S = \{2^i| i \in \mathbb{N}\}$ prove that ...
1
vote
0answers
35 views
Prove the ternary representation of there natural numbers is not a regular language [duplicate]
Choose some set in the natural numbers such that the language formed by the set under binary representation is a regular language, but is not regular under any other language formed by some base. ...
0
votes
0answers
25 views
Prove that any PDA/CF language with 1 character is regular [duplicate]
I know there is a post like this already posted, but I didn't quite understand the proof. Can someone explain it to me? Thanks in advance.
1
vote
1answer
18 views
Proving set of finite languages vs all languages over finite alphabet to be countable / uncountable
I came across following facts:
Set of finite languages over a finite alphabet is countable.
Set of languages over finite alphabet is uncountable.
I believe proof of this will be similar to ...
0
votes
0answers
22 views
Reducing universal language to language of palindromes
I am trying to understand proof for proving language of all palindromes is undecidable from these slides. It tried to reduce universal language to language of all palindromes on alphabet.
The two ...
-1
votes
0answers
16 views
I want to create an unsigned 8-bit adder/substractor and implement it in a logic circuit [closed]
I am having a hard time trying to implement an adder for 8-bits unsigned numbers with 1's complement but without using VHDL since I am new to this kind of stuff. But I know that I should use 8 full ...
0
votes
0answers
25 views
A TM that doesn't decide Σ*, and a TM that doesn't decide the empty set?
I was wondering if it was possible to create a TM that semi-decides (but doesn't decide) either of the following two languages:
$\emptyset$
$\Sigma^{*}$
I assume for 2, a one-state TM that just ...
2
votes
1answer
65 views
Can there be a context free language that is not recognizable by a PEG?
This is related to this question. Essentially, I want to know whether my reasoning is correct.
We know that parsing with a context free grammar is same as boolean matrix multiplication (forward: ...
0
votes
1answer
34 views
Proving a language is not Semidecidable
I have the language $L = \{ \langle M_1, M_2 \rangle : L(M_1) \subset L(M_2)\}$ and I'd like to prove that it is not Semidecidable. To do so, I need to use a reduction from $\neg H$. I cannot use Rice'...
4
votes
1answer
57 views
Can every regular expression be written as sum of products?
I was trying to prove that Parikh Image of every regular language is semi-linear. Even though it is true for CFL, but this question was about regular languages.
To prove this, I decided to proceed as ...
1
vote
0answers
17 views
Is ASM a regular language?
I'm giving a presentation where I have a single slide dedicated to formal languages. In this slide I give a simplified overview of the Chomsky Hierarchy and I'd like to give an example of a real world ...
0
votes
1answer
44 views
Statements about homomorphisms
Consider the following expressions about homomorphisms and show if the statements are true or not.
Σ={0,1}, L1 and L2 are Languages ⊆ Σ*, and ᵠ is a homomorphism ᵠ: Σ* → Σ*.
ᵠ(L1 ∪ L2) = ᵠ(L1) ∪ ᵠ(...
2
votes
3answers
67 views
How to prove that this language is not regular?
Given a language $L$ over the alphabet { 0, 1, [, ,, <...
0
votes
1answer
59 views
Is it decidable “Given a TM M, whether M ever writes a non blank symbol when started on the empty tape.”
I came across below problem in this pdf:
Given a TM M, whether M ever writes a non blank symbol when started on the empty tape.
Solution given is as follows:
Let the machine only writes blank ...
1
vote
2answers
37 views
Difference between $a^{2n} b^n$ and $n_a(w) = 2n_b(w)$
I have encountered two questions related to npda:
Construct an npda for $L_1 = \{a^{2n} b^n \mid n \geq 0\}$ as a language over $\Sigma = \{a,b,c\}$.
Construct an npda for $L_2 = \{w \in \{a, b, c\}^*...
0
votes
1answer
46 views
Formal languages: What is $2n_c$?
I have got following question:
Determine whether the following language is context free or not:
$$L = \{ w \in \{a,b,c\}^*: n_a (w) = n_b (w) = 2n_c (w)\}. $$
What is the meaning of $2n_c$ in the ...
0
votes
0answers
24 views
universal turing machine encoding
i am trying to learn universal turing machines. and i am stuck at encoding tm's. here i am trying to simulate a PDA. and one of transitions is below.
is there a specific rule that "there can not be ...
0
votes
0answers
11 views
can a PDA without lamda-transition accept every context free language? [duplicate]
I want to know if every context-free-language can be constructed with a PDA without lambda transitions. I have tried to give a counter example but couldn't.
Is there a theorem proving such statement ...
1
vote
1answer
42 views
Quotient of languages, regular quotient and their closedness
Left quotient is defined as below at this link:
Left quotient of $L1$ by $L2$:
$L1\backslash L2:= \{u\in \Sigma^*|vu\in L1$ for some $v\in L2 \}$
Wikipedia defines it as follows:
$L_1\...
1
vote
1answer
24 views
Given a regular language, calculate its equivalence classes
I was given the following regular language:
For any $n$, the language $L_{n}$ consists of all words over $Σ = \{0, 1\}$ whose $n$th character
from the end is 1.
I know it's regular because it can be ...
2
votes
1answer
89 views
Example of two undecidable languages that cannot be reduced to each other
I want to find two undecidable languages $A$ and $B$ that $A$ cannot reduce to $B$, $B$ cannot reduce to $A$(Many-one reduce). One of my thought is to let $A$ be the halting problem, let $B$ be some ...
0
votes
2answers
44 views
Halting problem vs Universal Language
Wikipedia defines halting set as follows:
$H = \{(i, x) |$ program $i$ halts when run on input $x\}$
Ullman defines universal language as follows
$U = \{(M, w) |$ Turing machine $M$ accepts $w\}...
1
vote
1answer
62 views
Prove that $\texttt{prefix}(L)$ is regular
Given that $L = \lbrace 0^n1^n : n \geq 0\rbrace$ is a non-regular context-free language, prove that $\texttt{prefix}(L)$ is regular.
So far I have provided that the grammar to produce this language ...
1
vote
1answer
33 views
Making a CFG for a^i b^j c^k such that i+k < 3j
I have the language $L = \{ a^ib^jc^k \mid i + k < 3j \}$, however I am struggling to convert it to a CFG.
I have thought about solving this for a long time but but this still hasn't gotten me ...
-2
votes
2answers
77 views
Why Rice theorem work for decidability?
Rice's theorem states:
Every nontrivial property of recursively enumerable language is undecidable.
I came across following problems, which Ullman's books say both are undecidable:
Turing ...
1
vote
2answers
77 views
Can I apply Rice's theorem to decide decidability status of these languages?
I came across these languages:
A Turing machine prints a specific letter.
A Turing machine computes the products of two numbers
I was guessing whether I can apply Rice's theorem to decide upon above ...
0
votes
1answer
37 views
No nonfinal states in NFA
I know that if there are no non-final states in DFA then the language accepted is $\Sigma^*$.
What will happen if there are no non-final states in an NFA? Can we say it also accepts $\Sigma^*$? Can ...
0
votes
1answer
44 views
Turing recognizable but not Turing decidable language cannot have TM do not halt on infinitely many inputs
Sorry, I think I misunderstand the question, It should read as if $L$ is turing-recognizable but not decidable, then there exists infinitely many input that any TM will not halt on it...
0
votes
0answers
42 views
Relating decidable, undecidable, recognizable, co-recognizable, unrecognizable, countable and uncountable languages
I went through a lot of texts and tried understanding various terms: decidable, undecidable, recognizable, co-recognizable, unrecognizable, countable, uncountable, enumerable and unenumerable.
Let ...
0
votes
0answers
14 views
Relating decidable, undecidable, recognizable, co-recognizable, unrecognizable, countable and uncountable languages [duplicate]
I went through a lot of texts and came up with following diagram to summarize the relation between decidable, undecidable, recognizable, co-recognizable, unrecognizable, countable and uncountable. Am ...
1
vote
1answer
97 views
What does it mean by “not recursively enumerable”?
I came across following therem:
There exists a recursively enumerable language whose complement is not recursively enumerable.
Now, I know following definitions:
Recognizable language is one ...
0
votes
0answers
24 views
Cook Levin Theorem (Sipser Proof) (phi move)
In Sipser's proof of the cook levin Theorem the move function (phi move) checks whether a given window is legal. For that we must have an exhaustive set of all possible legal windows to verify that a ...
0
votes
1answer
82 views
What programming languages always learned in computer science B.Sc.?
Even if programming by itself is not an integral part of computer science,
I would bet any B.Sc. student learns fundamentals of binary code, fundamentals of assembly code and at least one high ...
2
votes
1answer
23 views
Recognizable vs co-recognizable languages
I understand following about recognizable (aka recursively enumerable) and co-recognizable languages:
Definition 1: Recognizable language is one which have one-to-one correspondence with the natural ...
1
vote
0answers
51 views
Prove that grammar $S \to aSc | \epsilon | bBc$ ,$B \to bBc | \epsilon$ generates language $\{a^ib^jc^{i+j} | i,j \ge 0 \}$
Prove that grammar $G$ with productions:
$S \to aSc|\epsilon | bBc$
$B\to bBc | \epsilon$
Generates language $ L = \{a^ib^jc^{(i+j)}$ | $i,j \ge 0 \} $
Step 1. Prove $L(G) \subseteq L$
.
...
0
votes
1answer
49 views
Maximum number of configurations of Turing machine after $n$ moves
I came across following question:
What are maximum number of configuration of Turing Machine after $n$ moves?
The answer given was:
$k^n$, where $k$ is a branching factor.
And that "branching ...
0
votes
1answer
41 views
Does every regular language have a linear grammar?
Some definitions and facts (from Wikipedia):
A linear grammar is a context-free grammar that has at most one nonterminal in the right hand side of each of its productions.
the left-linear or left ...
0
votes
0answers
20 views
Is the language $L$=$\{<D_1,D_2> | D_1,D_2$ are DFAs over $\{0,1\}$ and $L(D_1) \subseteq L(D_2)\}$ decidable?
I came up with an algorithm to decide this language, but not sure if it is correct?
...
7
votes
2answers
2k views
Language to define perfectly a programming problem
Is there any language, which can be used to define all programming problems perfectly?
By perfectly, I mean with these two properties:
p is the problem.
d is the definition in the language.
P(d, p): ...
6
votes
1answer
252 views
Are these special (one production) Context-Free Grammars always unambiguous?
Consider the following (Context-Free) Grammars with only one production rule (not including the epsilon production):
$S \rightarrow aSb\;|\;\epsilon$
$S \rightarrow aSbS\;|\;\epsilon$
$S \rightarrow ...
1
vote
1answer
42 views
What kind of language does the following DFA accept?
can anyone please describe the language this FA accepts? thank you
1
vote
1answer
90 views
Is my formal definition of programming language correct?
I found this formal definition of a programming language in the 1973 paper Formal definition of programming languages by Terrence Pratt.
PL is a formal language endowed with two structures: a ...
0
votes
1answer
31 views
Why is this grammar ambiguous?
S ::= x
S ::= if E then S
S ::= if E then S else S
This is example if E then if E then x else x proves that it is ambiguous ...
2
votes
1answer
38 views
Does this argument prove CFLs are not closed under union?
Context free languages are not closed under complementation. This follows from their property of non-closure under intersection:
If CFLs were closed under complementation, then they must have also ...
2
votes
2answers
99 views
Grammar and Real-numbers
I am curious about following question. I've read other threads but the problem is slightly different:
Is the set of real numbers a language?
So my question is:
If I have a grammar, as defined in ...
2
votes
2answers
103 views
Prove that the following language is not regular: $\{0^i1^j : i \neq j\}$ [duplicate]
I was trying to approach this proof, after multiple reads and attempts I am getting nowhere. If someone could help me out that would be great. Should I use the pumping lemma, if so how show I start, ...
2
votes
1answer
41 views
How do I call a system like a grammar, but where a rule has to be applied to all matches at once?
For example, given rules $\{ a \to x, a \to y \}$ and input $aa$ , I am usually allowed to derive strings $\{ xx, xy, yx, yy \}$. I would like to restrict this to only performing "consistent" rewrites,...
5
votes
3answers
134 views
How do I calculate the Nth result of a context-free grammar?
Given a context-free grammar and a maximum depth, how do I directly compute the Nth sentence without calculating or caching intermediary sentences?
Take as an example the following grammar:
(from ...
