Questions tagged [formal-languages]
Questions related to formal languages, grammars, and automata theory
2,175
questions
0
votes
0answers
24 views
How to do a Reduction?
I have to do the following exercise:
Can the following language be decided? Can the sentence of Rice be applied? Justify your choices.
L:={v|v is Code of a Turing machine and when entering λ an a ...
1
vote
1answer
31 views
Union of halting-like problem and non-halting-like problem
I came across the following problem:
Define languages $L_0$ and $L_1$ as follows :
$L_0=\{⟨M,w,0⟩∣M\text{ halts on }w\}$
$L_1=\{⟨M,w,1⟩∣M\text{ does not halt on }w\}$
Here $⟨M,w,i⟩$ is ...
3
votes
2answers
57 views
Why the most dominant programming languages didn't follow CSP thread model?
I was trying to ask this question in StackOverflow, but later realized that this question is more relevant to general computer science, not specific engineering problems. If you think it's not, please ...
2
votes
0answers
57 views
Which of these languages is regular? The Pumping Lemma seems to show none are
I've been reviewing past paper questions for an automaton course, and came across a question which effectively asks, which of these languages is regular?
$$
\{\ 0^m1^{(m \times n)}0^n\ \colon\ m,n\ge ...
1
vote
4answers
121 views
Does infinite length strings lead to uncountable languages?
This answer says:
We can have uncountable languages only if we allow words of infinite length.
So does that means any (finite / infinite) language or any (finite / infinite) set of languages over ...
0
votes
0answers
23 views
Is it decidable whether Turing Machine never scans any tape cell more than once when started with given string
The problem:
Is it decidable that the set of pairs $(M,w)$ such that TM $M$, started with input $w$, never scans any tape cell more than once.
How can I easily prove above to be decidable. I found ...
0
votes
1answer
45 views
Is it decidable if there exists some input such that the TM makes at least five moves?
I am reading this excerpt from Ullman's book:
I have following doubts:
(related to red underline) TM can make 5 left moves or 5 right moves. So it will need at max 11 cells. Then how it says 9?
(...
-2
votes
0answers
21 views
Prove belonging to log-space uniform
Consider words of the form $w_1w_2...w_{2^m}$, where all $w_i$ are words of length $m$ over $\Sigma = {{0, 1}}$. Let $p$ be the set of those words ofthis form in which the words $w_i$ are pairwise ...
0
votes
2answers
48 views
When Turing Machine behaves like Finite state automaton
I read following:
Turing Machine with finite (fixed sized) tape is essentially Finite state automaton.
Is this fact correct? My doubt is Turing Machine can go infinite loop even on finite tape if ...
2
votes
1answer
44 views
Closure properties of non-context-free languages (concatenation & complement)
I am trying to proof the properties of the complement and concatenation of two non-context-free languages $L_1$ and $L_2$.
I believe that both of these languages are closed under complement and ...
0
votes
1answer
46 views
Exact meaning of metalinguistic variable
Consider the following BNF
<join-command> ::= <string> + <string>
In this context <join-command> and <...
1
vote
1answer
34 views
What's the difference between phi and lambda in regular expression?
I've been learning on Formal Languages and Automata of Peter Linz(6th edition).
In the chapter 3 of this book, it explains the primitive regular expression.
But I don't know what is the difference ...
0
votes
1answer
19 views
Textbook for understanding formal grammars
I am looking to understand the Chomsky Hierarchy. I've read some textbooks that touch on formal grammars (textbooks on computability, which relate automata to specific sets of formal grammars, notably ...
0
votes
0answers
22 views
Proving sets of regular expressions and context free grammars are decidable [duplicate]
Consider below languages:
$L_1=\{<M>|M$ is a regular expression which generates at least one string containing an odd number of 1's$\}$
$L_2=\{<G>|G$ is context free grammar which ...
0
votes
0answers
20 views
Understanding PDA for odd length string with middle symbol 0
I came across this pdf, which describes the language of odd length string with middle symbol 0 as follows:
Doubts:
I dont understand the transition labels. In standard resources like books by ...
-1
votes
0answers
65 views
DFA that accepts all the strings that either begin or end (or both) with 01
I came across following problem:
Minimum number of states in DFA that accepts all the strings that either begin or end (or both) with 01 over the alphabet {0,1} = ?
I first tried to prepare two ...
1
vote
1answer
40 views
TM1 accepts w1 vs TM1 halts on w1
What is difference between following two problems, their decidability and recognizability status:
Given Turing Machine TM "accepts" given string w.
Given Turing Machine TM "halts on" given string w.
...
1
vote
0answers
33 views
Empty string in language with grammar in Chomsky normal form
In their book, Ullman et al says:
Every nonempty CFL without $\epsilon$ has a grammar $G$ in which all productions are in one of two simple forms, either:
$A\rightarrow BC$, where $A,B$ and ...
0
votes
0answers
13 views
Which of the following are regular languages? [duplicate]
Which of the following are regular?
$\{a^lb^mc^n|10000>l>m>n\}$
$\{w| \Sigma=\{a,b,c\},10000>n_a(w)>n_b(w)>n_c(w)\}$ where $n_x(w)$ is number of $x$ in $w$
I feel 1st ...
4
votes
1answer
309 views
Prove that the class of CFG languages that are closed under reversal is undecidable
Note
The wording of the title may be a bit vague, but I'm not asking if CFLs are closed under reversal. Please see below.
Problem Description
Given a word $w$, define $w^{r}$ to be its reversal.
...
0
votes
1answer
59 views
Why LL(1) grammar generate all regular languages?
I came across following:
Every regular language has right linear grammar and this is LL(1). Thus, LL(1) grammar generates all regular languages.
I tried to get that.
Definition: Right linear ...
1
vote
1answer
38 views
Is concatenation of regular language with any other language regular?
I came across following problem:
True or false?
If $L$ is a regular and $M$ is not a regular language then $L.M$ is necessarily not regular.
The answer given was:
Consider $L$ to be $\...
2
votes
1answer
64 views
Is SAT a single language or a union of languages?
I know that a language is in NP if a Turing machine can decide the language of its checking relation $\{\text{boolean formula }\#\text{ truth assignment | truth assignment is correct}\}$ in polynomial ...
1
vote
1answer
25 views
Non-deterministic Turing machine for $L_1 = \{w\#0^n|w \text{ is a suffix of some $x$ in $L$ with } |x|=n\}$
Show if L is in NP, then also L1 is in NP
$$L_1 = \{w\#0^n|w \text{ is a suffix of some $x$ in $L$ with } |x|=n\}$$
I know that if L is in NP, then there exists a NTM $M_L$ than accepts $x$, ...
1
vote
2answers
55 views
Turing machine that accepts $L = \{a^{n^2} | n ≥ 1 \}$ [duplicate]
I have the following language:
$L = \{a^{n^2} | n ≥ 1 \}$
I am trying to construct a Turing machine that accepts L. My basic idea (without success) is to use a 2-tape TM where in the 2-tape ...
0
votes
0answers
10 views
PDA for L = {d^(2n+2m) a^n b^m | n, m > 0}? [duplicate]
I'm really unsure how to tackle this. If I try pushing to the stack for all d's read, then I won't be able to pop all the elements when I get to the a's and b's.
0
votes
1answer
30 views
Deterministic pushdown automaton for a given language
I am trying to make a deterministic pushdown automaton from this language but without success.
Here is the language definition:
$\ L=\{0^n 1^m a^i b^j \ /\ m,n,i,j > 0 \ and \ m+n=i+j \} $
...
0
votes
1answer
40 views
Using the pumping theorem to show that this language is not context-free
Let $\sigma = \{a,b,c\}$ and let $L = \{s | s = a^jb^jc^k\}$ where $k=i*j$ and $i,j \geq 0\}$. Using the pumping theorem, prove that $L$ is not context-free.
I really don't know where to start, here. ...
2
votes
1answer
33 views
How does $LL(n)$ languages compare with $LR(0)$, for $n>0$?
In the context of languages (not grammars), I know following:
$LL(0) \subset LL(1) \subset LL(2) \subset \cdots \subset LL(k)$
$LR(0) \subset SLR(1) = LALR(1) = LR(1) = SLR(k) = LALR(k) = LR(k)...
2
votes
2answers
88 views
Grammar with fewest variables
I am looking over a past exam for a theory of computation class I am taking, and unfortunately no solutions are provided. I am stuck on this question, and would greatly appreciate any help or hints.
...
-1
votes
2answers
116 views
Uniqueness of solution in Arden's theorem
Geeksforgeeks contains a proof of Arden's theorem, asserting that $R=QP^*$ is the unique solution to $R=Q+RP$. The proof is reproduces below.
My question is:
What is the logical reasoning to prove ...
0
votes
1answer
30 views
What is the relation between a programming language and the language of its input?
I find some references say that
all the features of programming language fall within what can be captured by context-sensitive grammars. In fact, no programming language known to humankind anything ...
3
votes
1answer
28 views
Converting DFA to RE with Arden's Rule
So I've searched around and found the algorithm to do so: How to convert finite automata to regular expressions? and I decided to test out the second-level response, Raphaels, and while I was getting ...
0
votes
0answers
27 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
106 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
40 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
36 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
27 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
40 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
29 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 ...
0
votes
0answers
28 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
72 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
46 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
61 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
31 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 ...
2
votes
3answers
70 views
How to prove that this language is not regular?
Given a language $L$ over the alphabet { 0, 1, [, ,, <...
1
vote
1answer
192 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
38 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\}^*...
1
vote
1answer
54 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
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 ...
