Questions tagged [formal-languages]
Questions related to formal languages, grammars, and automata theory
2,339
questions
-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 ...
