Questions tagged [formal-languages]
Questions related to formal languages, grammars, and automata theory
0
votes
1answer
46 views
Reusing variable in converting grammar to Chomsky Normal Form
I'm not sure if reusing variable is allowed in CNF.
For example, I have this grammar not in CNF. So I have to convert it to CNF.
...
2
votes
1answer
70 views
How does this answer for automata and Hamming distance not lead to inconsistencies?
I had already been given the answer by the TA in class, but I don't understand it. I'm not asking for the answer on a homework problem or anything.
The problem:
The Hamming distance ("distance") of ...
0
votes
1answer
31 views
Strings which are not in a language generated by a Grammar
I have the following question and its solution
Here T -> XTX
since T -> X and X->b
S ->XbX
since X->a
S->aba
So,why is option 3 not accepted ?
1
vote
0answers
20 views
Generalization of formal grammars - production rules with more general functions?
Usually formal grammars have production rules in the format N=tNt where simple concatenation function is used for the expansion of the nonterminal. https://www....
1
vote
0answers
84 views
How to design a LL(1) grammar for basic regular expression?
I try to design a LL(1) grammar to parse the basic regular expression. Here's the origin grammar.（\| is the escape character, since | is a special character in grammar's pattern).
...
1
vote
1answer
53 views
Proving that L is not regular by showing that $\equiv_L$ has infinite index
Proving that L is not regular by showing that $\equiv_L$ has infinite index.
$\Sigma$ = {a}, L = {$a^{3^n} : n \geq$ 0}
My ideas:
theorem of Myhill-Nerode: L $\in$REG $\Leftrightarrow$ $\equiv_L$ has ...
1
vote
1answer
57 views
context free grammar for palindrome: $L_n = \{x \in \Sigma^* | x = ywz, w^R = w, |w| \geq n, |y| = |z| \}$
Let $L_{n} = \{x \in \Sigma^* | x = ywz, w^R = w, |w| \geq n, |y| = |z| \}$
Generate a cfg of $L_n$
For n = 1, 2, 3
Informally, x is in $L_n$ means
some palindrome of at least length n is a ...
1
vote
1answer
34 views
What is the minimum pumping length of the union of two languages?
If I have two languages L1 and L2 that are pumpable, what is the minimum pumping length for the union of them?
Does it differ if either of them contains just one string like 001?
1
vote
2answers
52 views
How to add decimals to formal grammar?
I have a formal language that describes digit production like
<digit> ::= 0|1|2|...|9
and I need to intruduce fraction to write decimals like ...
0
votes
1answer
237 views
A,B decidable: proof that A\B is decidable too
For an assignment I have to proof that for two given decidable languages A,B, A\B is decidable too.
My idea is as follows:
If B is empty or doesnt have elements in common with A, then A\B is ...
1
vote
2answers
390 views
Minimizing DFA - Dead state elimination
Following is a Question from a competitive exam, it is given that the solution is A but I don’t know why the dead state 4 is not eliminated.Dead states like 4 which has transitions only to itself, ...
3
votes
0answers
15 views
Base-k representations of polynomials: state of art [closed]
In chapter 4 of Jeffrey Shallit's A Second Course in Automata Theory the following problem is formulated as open:
Let $p(n)$ be a polynomial with rational coefficients such that $p(n) \in \mathbb{N}$ ...
2
votes
1answer
69 views
What is the regular expression for the following language?
What is the regular expression for the following language?
$$L = \{acbc: a,b,c \in \{0,1\}^+ \}$$
maybe we can say $$L = ((0 + 1)^+ 0 (0 + 1)^+ 0) + ((0 + 1)^+ 1 (0 + 1)^+ 1)$$
Is it true??
1
vote
2answers
52 views
Regular expression for words where the same symbol can repeat at most two times consecutively?
Having the alphabet $\{a, b\}$, how can I generate a regular expression for the language that does not have substring of three or more consecutive same symbol?
For example, I can't have ${baaab}$ nor ...
3
votes
1answer
653 views
Does a notion of a context-free complete language exist?
Is there a notion of a context-free complete language (in the analogous sense to a $NP$-complete language)?
1
vote
3answers
184 views
Is the union of 2 non context free languages always non context free?
Let $L_1 = \{a^nb^nc^n\}$
and $L_2 = \{a^ib^jc^k \mid i\ne j\text{ or }j\ne k\}$ (which I think is a non Context free but I am not sure)
So, $L_1 \cup L_2$ will give $L_3 = \{a^*b^*c^*\}$ which is a ...
3
votes
3answers
130 views
Is the power of a regular language regular? Is the root of a regular language regular?
If $A$ is a regular set, then:
$L_1=\{x\mid\exists n \geq0, \exists y \in A: y=x^n\}$,
$L_2=\{x\mid \exists n \geq0, \exists y\in A: x=y^n\}$.
Which one of them is regular?
My reasoning is since ...
1
vote
1answer
23 views
Can a context-senstive gramma contains production rule $cB\rightarrow Bc$?
Some textbook show that the grammar $G=(N,T,P,S)$ below belongs to context-senstive grammars:
S->aSBC
S->abc
cB->Bc
bG->bb
where N={S,B}, T={a,b,c}.
I am confused by the fact that the production ...
1
vote
1answer
168 views
Proving $L = \{a^nb^m \mid n, m≥0, n \neq m\}$ is not regular by use of Pumping Lemma
I've been struggling with this problem for quite a while now and every explanation I have managed to find doesn't seem to correctly solve it.
Question
Proving $L = \{a^nb^m \mid n, m≥0, n \neq m\}$...
1
vote
1answer
98 views
Pumping Lemma Question: About the cases for y in the xy^iz criterion
Problem statement:
Let $\Sigma = \{a, b, c\}$, and consider the task of multiplication encoded in the language $L = \{a^n b^k c^{nk} : n \geq 0, k \geq 0\}$.
Prove that L is not regular using the ...
1
vote
0answers
74 views
Is $\{a^mb^nc^{mn}\mid m>n\}$ a context-free language? [duplicate]
Been trying to figure it out for an hour myself and another hour looking around, I cannot find anything with the $c^{mn}$ part.
$$L=\{a^mb^nc^{mn}\mid m>n\}$$
0
votes
1answer
47 views
Context-Free Grammar from this language
I'm having difficulties with an exercise in a theoretical CS class.
The problem is:
let $L_{2}$ be a language defined as follows: after every "a" come atleast two "b" or after every "b" comes atleast ...
3
votes
1answer
45 views
unambiguous context-free languages and complementation
I was considering the following two natural questions about the relationship between unambiguity and complementation for the class of context-free languages:
Is the complement of an unambiguous ...
0
votes
1answer
151 views
If a language has a regular grammar, is it regular?
If L has a regular grammar, is L always a regular language?
A regular grammar is a formal grammar that is right-regular or left-regular. Every regular grammar describes a regular language.
So would ...
1
vote
1answer
75 views
When is the concatenation of a language $L$ with $\Sigma^*$ regular?
I've been looking at questions about the regular concatenation of two languages; one question said that the concatenation of $\{0^n1^n|n\geq 0\}$ and $\Sigma^*$ was regular (over the alphabet $\Sigma =...
1
vote
1answer
71 views
Find equivalence classes of language $L = \{0^n1^n, n \in \mathrm{N}_0 \}$
I'm asked to find all equivalence classes of the language
$$L = \{0^n1^n, n \in \mathrm{N}_0 \}$$
We have the following definition:
$$(xR_Ly)\Leftrightarrow (\forall w\in \Sigma^* xw\in L \...
1
vote
1answer
338 views
CFG for language of all palindromes whose number of 1s is divisible by 3
The question is the following:
Construct a CFG for $L_2 = \{w ∈ {0, 1}^* \mid w = w^R\text{ and the number of 1’s in $w$ is divisible by 3}\}$.
I can construct a CFG for $\{w \in \{0,1\}^* \mid w =...
2
votes
1answer
147 views
Regularity of language of words containing a square
$$L = \{w\mid w\text{ contains a substring of form }yy\text{, where }y\text{ is any non-empty string}\}.$$ Is this language regular? We do not know what $y$ looks like in advance. And why is this ...
0
votes
1answer
55 views
Can an alphabet be $\{ε\}$ or $\mathbb{N}$?
Hopcroft says it is a finite nonempty set of symbols.
$\varepsilon$ (empty string) is not an ordinary symbol.
$\mathbb{N}$ is not finite.
So, no to both?
On the other hand, I do not see why $\{\...
2
votes
2answers
336 views
PDA to accept language with more a's than b's and c's
My question is similar to this one. I was wondering if a PDA exists, that accepts any words containing a's, b's and c's in a random order, where the total amount of a's is higher than the amount of ...
1
vote
1answer
57 views
Inductive approach on Kleene star proof
I'm having trouble proving the following: If $L_1$ and $L_2$ are languages then: $$(L_1^*L_2^*)^* = (L_1\cup L_2)^*$$
I could be on the wrong track here, but I figured an inductive approach is a good ...
3
votes
1answer
86 views
Find a regular grammar that generates words with even number of a's
I have a language $L$ = {$vabu$ | $v$,$u\in \{a,b\}^*$, $|vu|_a = 0$ $($mod $2)$$\}$
where $|vu|_a$ is number of $a$ in $vu$.
I came up with these rules:
$\sigma \rightarrow aa\sigma | ab\xi$
$\...
2
votes
3answers
64 views
Given an CFG determine if $\varepsilon \in L(G)$
Given a context free grammar how am I able to determine if $\varepsilon \in L(G)$ ?
The only way I thought of is to systematically check if I can derive the empty word from the given grammar. (...
1
vote
1answer
43 views
Is my pumping lemma proof correct? [duplicate]
Show that $L = \{a^nb^l \ | \ n \leq l \}$ is not regular
I'd like to check if my proof for this is correct.
Proof: Choose any positive integer $m$. Pick $w = a^mb^{m+1} \in L$. Note that $|w| = 2m+...
1
vote
1answer
150 views
Is the problem of determining whether a CFG generates a string in the form 0*1* decidable?
Given a grammar $G$, is it decidable whether $G$ generates any string in the form $0^*1^*$? Why?
I think it's undecidable but can't find any undecidable problem to reduce it to.
0
votes
2answers
166 views
Non-regular language whose prefix language is regular
I understand that prefix of a regular language is regular, but I am unable to get my head around this:
Give an example of a non-regular language $A ⊆ \{0, 1\}^*$ for which $\operatorname{Prefix}(A)$...
1
vote
1answer
89 views
Prove that every CFL has at least one infinite equivalence class
If we define the Myhill-Nerode relation on a CFL how can i prove that there is at least one infinite equivalence class?
-1
votes
1answer
143 views
What is an infinite language?
I just started reading about formal language theory and what i have learnt so far that:
Alphabet is a finite set of symbols.
String/Word: is always finite.
Because a language is set of strings of ...
3
votes
3answers
123 views
If $L$ is a regular language, then $s(L)$ is also regular
...where $s$ is a substitution that replaces each symbol of each string in $L$ with a regular expression.
For example, if $L=a^*b$ and $s(a) =ab, s(b) = b^*$, we have $s(L) = (ab)^*b^*$.
My ...
0
votes
1answer
43 views
Different iterations of regular expressions
A four-part question dealing with formal languages and regular expressions:
How many basic regular expressions (using only the rules 0/ϵ, 1/∅, *, +, and •) are there to match a given string?
How ...
0
votes
3answers
711 views
is this language regular and why pumping lemma doesn't work?
I was told that this language is regular but as I can show below, pumping lemma is not working for it. What am I doing wrong? Is this language really regular? Why?
0
votes
2answers
75 views
Does there exists a finite automata for the given language?
The question is simple and given as, $alphabets=\{a, b\}$, and language $L$ over them as:
$L = \{w: w \ € \{a, b\}^*, (n(a) - n(b)) \ mod \ 3=1\}$. Here $n(a)$ = number of $a$ and $n(b)$ is number of ...
5
votes
1answer
264 views
About the relationship between non-termination and inconsistency?
I've been trying to get into Agda and I noticed that it doesn't have recursion, which implies that it isn't Turing-Complete.
From what I could understand, if Agda had recursion, it would make itself ...
1
vote
3answers
133 views
What is a non-ambiguous CFG for generating the set of natural numbers?
I'm trying to write a non-ambiguous context-free grammar that can generate the set of natural numbers, including the 0. My current solution is the following grammar:
$\mathcal{G}: S \rightarrow 0\ |\ ...
2
votes
1answer
181 views
Is there a polynomial time algorithm to tell if an NFA over an unary alphabet is universal?
Given an Nondeterministic Finite State Automaton with $n$ states over an unary alphabet, is there some algorithm to check if the automata is universal in time polynomial in the number of states?
I ...
2
votes
1answer
61 views
Proving formula for derivative of Kleene star
Prove that for any symbol $a$ and regular expression $r$ it is true that:
$$\partial a(r^* ) = \partial .a(r)(r^* )$$
My attempt:
Induction on regular expression $r$
Base cases:
1) $\...
2
votes
3answers
419 views
Are all finitely recursive context free languages parseable with a regexp?
Let's say I have a context free language. It can be recognised by a pushdown automaton. Chances are it can't be parsed with a regular expression, as regular expressions are not as powerful as pushdown ...
-3
votes
1answer
233 views
Is mathematics context-free?
Anyone who deals with mathematics knows intuitively that it is a different kind of thinking than ordinary common-sense thinking that intelligent people use every day to understand and make decisions ...
1
vote
2answers
103 views
How to determine maximum stack size of LL(1) parser?
I am generating an LL(1) parser generator for LL(1) grammars that have a maximum stack size when executed in the table-driven parser. Specifically, I'm parsing HTTP headers using a parser generated by ...
1
vote
1answer
48 views
Proving equivalency of regular expressions
x,y are regular expressions, prove this:
(xy+x)$^*$x = x(yx+x)$^*$*
(* in this expression is kleene star)
I am looking for a method that is applicable to prove such questions.
I know that proof ...
