Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

Filter by
Sorted by
Tagged with
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 ...