Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

Filter by
Sorted by
Tagged with
-3
votes
0answers
27 views

Question relating to NFA

Is there any NFA that can accept every alternate symbol in a given string. Ex. if w = abab, the NFA should accept bb
1
vote
1answer
20 views

Proof that languages are Turing-recognizable iff computably-enumerable

A very small question on this proof, which I found as Theorem 3.21 in Sipser's, and in my lecture notes. In the "only if" direction, we assume that a Turing machine $M$ recognizes some ...
1
vote
2answers
24 views

Can you say anything interesting about a language knowing only that it is prefix-closed?

Suppose $L$ is an arbitrary formal language over a finite alphabet $A$, and suppose that $L$ is closed under prefixes (i.e. if $w \in L$, and $u$ is any prefix of $w$, then $u \in L$). Knowing only ...
0
votes
0answers
16 views

Show {𝑎^i𝑏^j𝑐^k, i!=j!=k} is context free or not, how can we prove it? [duplicate]

I stuck on this question for a long time and cannot figure out how to prove it?
0
votes
0answers
21 views

Show {𝑎^i𝑏^j𝑐^k, 𝑖!= j and 𝑗 != 𝑘} is a context-sensitive language, what is the grammar? It is context free or nor?

I've been pondering this question for a long time, that 𝑎^i𝑏^j𝑐^k, 𝑖!=j and 𝑗 != 𝑘 is a context-sensitive language, how we can prove it to be context sensitive or which grammar can generate such ...
4
votes
1answer
610 views

Is every unambiguous grammar regular?

While searching for an answer to this question I found out that there is an unambiguous grammar for every regular language. But is there a regular language for every unambiguous grammar? How can I ...
0
votes
1answer
30 views

Can this language be called regular?

Recently, I was facing some problems in effectively proving the following : Consider the alphabet Σ ={0,1,2,...,9,#}, and the language of strings of the form x#y#z, where x,y and z are strings of ...
0
votes
1answer
40 views

a^ib^jc^k, i < j < k is a context-sensitive language, how can prove it as a context sensitive

I've been pondering this question for a long time, that $a^ib^jc^k, i < j < k$ is a context-sensitive language, how we can prove it to be context sensitive or which grammar can generate such a ...
0
votes
0answers
17 views

Do the SLR and LALR parsers of a same CF grammar have the same shift actions?

In theory, given that: The LALR parser can be constructed by merging LR(1) states with the same core; If $I$ is a LR(1) set of items, then $\text{core}(\text{GOTO}(I))=\text{GOTO}(\text{core}(I))$; ...
0
votes
2answers
80 views

How to understand and apply pumping lemma to prove $a^{i+1} b^{4i+2}$ is not regular?

I am having trouble understanding how to apply Pumping Lemma to show a Language is not regular. If the alphabet is $\Sigma = \{a, b\}$ and the language is $L = \{a^{i + 1} b^{4i + 2} \mid i \in \...
1
vote
1answer
25 views

Construct a DFA recognizing a language $L$ that has exactly $I(L)$ states

Let $L$ be a language, and consider the following relation $\equiv_L$ on strings: $s_1 \equiv_L s_2$ if and only if, for every string $w$, we have that $s_1w \in L \Leftrightarrow s_2w \in L$. This is ...
0
votes
1answer
31 views

What becomes of context-sensitive grammars if $\epsilon$ productions are allowed?

The original formulation of the 3 restricted grammar types of Chomsky all included the restriction that the right-hand side of a replacement cannot be $\epsilon$ (non-contracting). This, however, can ...
1
vote
2answers
44 views

Proving non-regularity via syntactic congruence classes?

Let $L$ be a language. The Myhill-Nerode theorem is based on the following equivalence relation: $$x \equiv_M y \Leftrightarrow \forall v \in \Sigma^*. (xv \in L \leftrightarrow yv \in L).$$ One ...
3
votes
0answers
34 views

BNF rule to regular expression

I'm looking for a way to find out whether a specific rule in a BNF grammar can be converted to a regular expression. (With "regular expression" (RE), I mean the simple mathematical kind. I'm ...
0
votes
0answers
19 views

ANTLR G4 grammer for math expression

I am new to grammar and have written grammar for parsing math expression for asciiMath using ANTLR as below. ...
0
votes
0answers
29 views

Constant single match regex

I am looking for the name (definition?) of X in: A regular expression is X iff it has exactly one possible match. Examples: <empty regex>, abc, ...
0
votes
0answers
20 views

Use of graph grammars/rewriting systems in compilers?

A(n imperative) program - in a higher-level language and more importantly in assembly language or intermediate representations like LLVM - can be formalized as a directed "port graph", in ...
1
vote
2answers
32 views

The intersection of 2 CFL

I have the following two CFL: $A =\{a^m b^n c^n\}$ and $B = \{a^m b^m c^n\}$. I don't understand why the intersection of this languages is $\{a^n b^n c^n\}$: can anyone explain to me why the power is ...
1
vote
1answer
54 views

Correct application of the CFL Pumping Lemma

I came across this question about showing that the language $L = \{w \epsilon \{a, b, c\}^*: n_a(w) + n_b(w) = n_c(w)\}$ is context-free but not linear in the book by Peter Linz. That is easily doable ...
0
votes
1answer
77 views

Algorithmic problem of regular, context-free, and recursively enumerable languages

Consider a language $L_1$ that is recursively enumerate, $L_2$ that is regular, and $L_3$ that is context-free. Are the following problems algorithmically decidable? Is $L_1 \cap L_2 = L_3$? Is $L_1 \...
3
votes
2answers
104 views

Is it possible to construct a finite state automata for a decimal adder?

Suppose the strings are of the form x#y#z , where x,y,z are strings formed from the alphabet $\Sigma=(0,1,2,3,4,5,6,7,8,9)$ . The language is accepted if x+y=z is satisfied, for example : 56#65#121 is ...
0
votes
1answer
37 views

Why is this language *not* pumpable? (language = arbitrary word followed by exact same arbitrary word)(pumping lemma for context-free-languages)

language = arbitrary word followed by exact same arbitrary word = u * u (with u being out of non-empty words of alphabet {0, 1} ) (sorry for the formatting, see screenshot-link for conventional/clear ...
0
votes
1answer
40 views

change turing machine to RAM

How can we convert a given Turing Machine into a Random Access Machine? I understand that we can use the transition function to come up with a sort of algorithm but how can we translate all of it into ...
0
votes
0answers
39 views

Is this grammar in Backus–Naur form?

I'm a newbie and a paper I'm reading specifies the following grammar: ...
0
votes
1answer
40 views

For an NFA, can we always find a RAM?

For an NFA, can we always find a RAM, which recognises the same language?
0
votes
0answers
40 views

The class of grammars recognizable by backtracking recursive-descent parsers

It is easy to show that there exists a grammar that can be parsed by a recursive-descent parser with backtracking but is not an $\text{LL}(k)$ grammar (consider any grammar with a production featuring ...
0
votes
1answer
51 views

Is the problem that determines whenever the word member $\in$ L(M) decidable or not?

Given a Turing machine M on alphabet {m,e,b,r} we're asked to determine if member $\in$ L(M). You must realize that M is not one specific machine and can be any turing Machine with the same alphabet. ...
0
votes
1answer
35 views

First-order mutual-recursive functions Turing-complete or incomplete?

Assume we have a C-like programming language with no pointer/heap semantics (i.e. there is no concept of memory; everything is on the stack). The only datatype supported is Integer, but suppose the ...
0
votes
0answers
25 views

Why is there no contradiction when using pumping lemma on a^N b^N a^2N, when k=2?

I have question where it asks: Using the pumping lemma on a^N b^N a^2N, why can you not reach a contradiction when k=2? Here's what I've done, but I do reach a contradiction... u=a^r v=a^s x=a^t b^N a^...
2
votes
1answer
32 views

GATE CSE 2009, Which of the following is FALSE?

This is a question from GATE CSE 2009. Which of the following is FALSE? A] There is a unique minimal DFA for every regular language. B] Every NFA can be converted to an equivalent PDA. C] ...
1
vote
1answer
26 views

Prove that the language is not regular through Myhill-Nerode Equivalence

The language is given by: $$L=\{a^nb^m|n<m\}$$ I have proven that the language is not regular using the pumping lemma but I need help with proving it through Myhill-Nerode Equivalence. Any help ...
1
vote
0answers
53 views

Is every language described by a grammar?

I read the following argument showing that not every language is described by a grammar: For a fixed alphabet $\Sigma$ and variables $V$ there are uncountable many languages over $\Sigma$ since the ...
1
vote
1answer
70 views

How to prove the language of all Turing Machines that accept an undecidable language is undecidable?

I want to prove that $L=\{\langle M \rangle |L(M)\text{ is undecidable}\}$ is undecidable I am not sure about this. This is my try : Suppose L is decidable. Let $E$ be the decider from $L$. Let $A$ be ...
1
vote
0answers
53 views

Number of words of length n for special language

Let $\Sigma$ be an alphabet and let $L$ be a language over it with the following properties: if $w\in L$ then there exists $v\in \Sigma^*$ such that $wv \in L$ and for every $s\in \Sigma$ the word $...
3
votes
1answer
97 views

If $A$ is context-free then $A^*$ is regular

I am currently studying for my exam and I am having trouble to solve this question: Right or wrong: If $A$ is context-free then $A^*$ is regular. I think it's wrong because if $A$ is context-free it ...
1
vote
1answer
13 views

Proof for values of d with d:= ||L|| - N(L) with $d \in \mathbb{Z}$ and N(L) Nerode Index

Let ||L|| be the sum of all lengths of words in L und N(L) the number of equivalence claesses for the Relation $\equiv_L$ from Myhill–Nerode theorem. Proof, which values d can have with $d:=||L||-N(L),...
0
votes
1answer
24 views

If a grammar G is left and right regular, why $||L(G)|| \leq ||P||$?

I was studying automata theory and formal languages and came across this question: If a grammar $G$ is left and right regular, why $||L(G)|| \leq ||P||$ ? I've searched the theory but I am missing ...
0
votes
1answer
77 views

Enumerator for Word and Halting Problem

in theoretical computer science I learned for every recursive enumerable language there would be an enumerator and a grammar. So since word problem and halting problem are recursively enumerable, I ...
1
vote
1answer
38 views

Is {<M>: L(M) ∈ NP} ∈ NP?

Intuitively I think the answer is no since I don't think every certificate can be checked in polynomial time but I don't know how to give a formal proof. Is the statement true? Why or why not?
0
votes
1answer
48 views

Is there a way to map the concatenation operation over strings to the addition operation over $\mathbb{N}$

Given an alphabet, say $\Sigma = \{0,1\}$, I can make a one-to-one mapping from all possible strings $x \in \Sigma^*$ to $\mathbb{N}$. This could be done by ordering $\Sigma^*$ lexicographically and ...
-1
votes
1answer
60 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 ...
5
votes
0answers
80 views

Growth function for non-regular languages

For language $L$ over an alphabet $\Sigma$ denote $\gamma_L(n)$ as the number of words of length $n$ in the language $L$. It is known that for regular languages this function represents a sequence ...
1
vote
1answer
42 views

Is a compiler a kind of Gödel numbering program?

Question: Is a compiler a kind of Gödel numbering program? Wikipedia tells us that a compiler is: "In computing, a compiler is a computer program that translates computer code written in one ...
0
votes
0answers
30 views

Automatic stack

Each context-free language has an automatic stack received by a non-deterministic blank. That is, it will not uphold the following determinism requirement:
-3
votes
1answer
56 views

Myhill-Nerode to prove a language is non-regular

L = {a^n b^2n c^3n | n∈N^+} I'm trying to prove that L is a non regular language using Myhill-Nerode theorem.
1
vote
1answer
44 views

Two languages such that their Kleene closures are equal

I am trying to solve the following problem: Find languages S and T over the alphabet $\{a, b\}$ such that $ S \not\subset T $ and $ T \not\subset\ S $ ($S$ is not contained in $T$ and not equal to $T$,...
3
votes
1answer
107 views

Largest set of 10-digit numbers where none have Hamming Distance = 1 with any other

I'm working on a system that will require manual data entry of 10-digit numbers (Σ = 0123456789). To help prevent data errors, I want to avoid generating any two ...
1
vote
1answer
698 views

Is it true that if L* is recursive, L is also recursive?

Is it true that if $L^*$ is recursive, where $*$ is Kleene star, $L$ is also recursive? I know that the opposite direction is true: If $L$ is recursive, then $L^*$ is recursive. But I don't know how ...
0
votes
0answers
39 views

Turning grammar to LL(1)

I have difficulty / doubt in transforming a grammar into LL (1), I tried remove left recursion but grammar still not LL(1). ...
3
votes
0answers
44 views

Are there context free grammars for all restricted Dyck paths?

A Dyck path is a finite list of $1$'s and $-1$'s whose partial sums are nonnegative and whose total sum is $0$. For example, [1, 1, -1, -1] is a Dyck path. Rather ...

1
2 3 4 5
47