Questions tagged [formal-languages]
Questions related to formal languages, grammars, and automata theory
2
votes
1answer
22 views
How to choose a word to apply the Pumping Lemma?
I have some questions about the PUMPING LEMMA.
First of all, I do not study computer science, I still go to school, but I'm very interested, so I could make mistakes.
And sorry about my English :)
...
0
votes
1answer
32 views
Chomsky Classification of Languages
Given is a language $A = \{ a^n\:b\:c^{2n}\:b^m |\; n ∈ N^{+} ;\; m ∈ N \}$ ; where $N^{+}$ are the natural numbers excluding 0.
I have found a type-1 grammar to describe it:
$S \to A_1A_2$
$A_1 \...
1
vote
1answer
51 views
Induction on strings (words)
Given is an alphabet $\Sigma = \{ 0, 1, 2 \}$ and a function quer to calculate the cross sum of a word.
$quer : \Sigma^*\to \Bbb N$ with:
$$quer(w)=\begin{cases} 0, &\text{when } w=\epsilon\\
...
0
votes
0answers
25 views
If there is comparison between two variables then language is not regular. Then how the below two languages L1 and L2 Regular? Please Explain [duplicate]
How these two languages be regular.If there is comparison between m and n since (n < m) is the condition to be satisfied.
1
vote
0answers
24 views
How to create model for a powerful language whose programs are guaranteed to terminate?
I'm creating a powerful regular expression matching system that can be augmented by adding small microprograms to deterministic finite automaton (DFA) states. The microprogram solves the big bang ...
1
vote
3answers
54 views
Give a grammar for words whose number of $a$'s modulo 2 is larger than whose number of $b$'s modulo 2
Given is an alphabet $\Sigma = \{ a, b, c \}$, and a language $A4 =\{ w \mid w \in \Sigma^* \wedge |w|_a \operatorname{mod} 2 \ge |w|_b \operatorname{mod} 2 \}$
whereas $|w|_a$ is the number $a$'s in ...
0
votes
1answer
19 views
How to generate a grammer from this language? [duplicate]
I'm trying to generate a grammar from this language:
L={a^i b^j c^k d^l : i+j=k+l}
to be clear its a in the power of i and b in the power of j... and so on, so ...
2
votes
1answer
47 views
How to prove a language is not regular using the Pumping Lemma?
I need some help with my proof, because I'm not sure if the following works. Tips and Tricks are welcome since this topic is completely new to me and very difficult.
Task:
Prove that $M = \left\{ a^...
1
vote
1answer
46 views
RAM BSS model based (or its variant) computer recognizing Boolean languages
Can any RAM BSS model based machine, or machines which are variants, recognize boolean languages(languages such as P, NP, or the like)? If so which languages are recognizable by RAM/BSS nachines, or ...
0
votes
2answers
31 views
Why is $\{a^nb^n \mid n \geq 1\}$ not type 3 (regular)?
My book states that the language
$$L_1 = \{a^nb^n\mid n\geq 1\}$$
is of type 2 (context-free) but not of type 3 (regular) since there is no regular grammar to produce it. However, I can't really ...
0
votes
0answers
14 views
What are some differences between regex (FSM) in computer science with regex in programming? [duplicate]
Computer science has automata theory with lessons on regular expressions and FSM. How are these different from regex engines used in programming such as C++, Perl, PHP etc.?
I would like to know some ...
1
vote
1answer
14 views
If you have a smallest grammar approximation, do you immediately have a CFG inference algorithm?
The smallest grammar problem is to find a single-string CFG. So given a finite list of language samples, known to all lie in some CFG, can we, using the smallest grammars (approximated) of each ...
-1
votes
2answers
33 views
How to construct Context Free Grammar of words with equal number of 0's and 1's [duplicate]
i am trying to find a cfg for this cfl
L = $\{ w \mid w \text{ has an equal number of 0's and 1's} \}$
is there a way to count the number of 0's or 1's in the string?
1
vote
2answers
56 views
Buchi automata in formal software verification
As I am studying the application of Buchi automata in formal software verification, I am interested in the computational complexity (or links to papers) for the algorithms used to solve the problem in ...
1
vote
2answers
50 views
Is every subset of a RE language also RE, in general?
I'm trying to understand the question in my title in an intuitive way:
If I have an RE language A, then some TM, say TM(A) accepts on it. If I take a subset of A, say A2, then all elements of A2 will ...
2
votes
2answers
375 views
Can a Formal Language be of a type (RE, REC, Regular, etc) for one TM, but of a different type for another?
I'm new to the study of formal languages, and I wondered if languages of a certain type are objectively of that type (RE, REC, regular, etc), or if their type varies on their context? I had this ...
1
vote
1answer
19 views
Set Difference of Two RE Languages - An Intuitive Idea of Why It's Not Closed
I'm new to studying formal languages, so apologies if I get a lot of basic stuff wrong, but I'm trying to get an intuitive understanding of why the difference between two Recursively Enumerable ...
0
votes
1answer
28 views
Why can't a left-recursive, non-deterministic, or ambiguous grammar be LL(1)?
I've learned from several sources that an LL(1) grammar is:
unambiguous,
not left-recursive,
and, deterministic (left-factorized).
What I can't fully understand is why the above is true for any LL(1)...
1
vote
0answers
27 views
Why full Chomsky hierarchy is so detailed, if there are decidable recursive languages?
One can have a look on the Chomsky hierarchy https://en.wikipedia.org/wiki/Chomsky_hierarchy , especially the inset named "Automata theory: formal languages and formal grammars" at the bottom of the ...
-1
votes
1answer
32 views
Verify this cfg is finite or not
S-> aAb | aBd
A-> ab | Bd | e
B-> ab | d | f
I am getting a loop during CNF conversion but in question it stated that it's a finite language.
1
vote
1answer
86 views
Can Deterministic Context free Grammars be ambiguous?
I know that DCFL are unambiguous languages and DCFL languages have one-to-one correspondence with LR grammars.
But I wanted to know if there can be an instance that deterministic context free grammar ...
0
votes
0answers
16 views
How to prove that models of indirect and direct RAM machines are equivalent?
as in the title, I am looking for a formal proof how to show that models of indirect and direct RAM (random-access) machines are equivalent. I would really appreciate your help.
0
votes
0answers
19 views
How to find follow sets in this question?
E -> TE’
E’ -> +T E’|Є
T -> F T’
T’ -> *F T’ | Є
F -> (E) | id
How to compute Follow(E),Follow(T),Follow(T’),Follow(E') and Follow(F)?
1
vote
2answers
87 views
Why are not all recursive languages undecidable?
I learned that recursive language are decidable; correct me if I am wrong. However, I have found some arguments that seem to contradict this. These may or may not be correct; please let me know.
If ...
0
votes
0answers
16 views
Converting context-free grammar to chomsky normal form and ait greibach normal form [on hold]
I am sorry , my English is not good.
My question is:
S->aAc|aSc
A->aAb|ab
I found this as CNF:
S0->DB|DC
S->DB|DC
A->DF|DH
B->AN
C->AN
D->a
F->b
H->AF
N->c
İs this correct answer for CNF ? I am ...
0
votes
0answers
19 views
Formal Class of Languages Describable by .NET Regular Expressions
This is sort of a computer science question and sort of a programming question. What is the name of the formal class of languages that can be described by .NET regular expressions (assuming it a well ...
3
votes
1answer
30 views
How is $L^* - \{\epsilon \} \neq L^+$?
I was asked which among the following is true:
$\Sigma^*-\{\epsilon\} = \Sigma^+$
$L^* - \{\epsilon \} = L^+$
As I can see, both $\Sigma^*$ & $L^*$ are sets. I thought both were true ...
1
vote
1answer
29 views
If a DFA were implemented as a circuit, what would the empty string correspond to as input?
Say we have a DFA like the one shown below that accepts the empty string, $\varepsilon$.
Also suppose the functionality of this DFA has been implemented as a circuit so that an led lights up ...
0
votes
0answers
19 views
Is the set of context free grammars that generate no words in co-RE? [duplicate]
Is the $\{ \langle G \rangle \mid L(G) = \emptyset \}$ recursively enumerable or co-recursively enumerable?
1
vote
1answer
14 views
Efficiency/Redundancy in Chomsky normal form
I have a context-free grammar with the following production rules, $S$ being the start symbol:
$$\begin{align*}
S &\to AB \\
A &\to a \\
B &\to a\end{align*}$$
Is this in Chomsky normal ...
0
votes
2answers
41 views
What is an example of a decidable language?
I know that if a language is regular or context free, the language is decidable. However, if a language is decidable does that imply that it is also regular or context free?
0
votes
2answers
109 views
Context free grammar for $\{ a^i b^n a^n \mid i \ge 0, n \ge 0 \}$
Give a context-free grammar for the following language: $\{ a^i b^n a^n \mid i \ge 0, n \ge 0 \}$
So far, this is the solution that I have been able to come up with, though I am not sure how accurate ...
0
votes
1answer
35 views
Need help understanding what co-recursively enumerable means
Lets say I have a set: $ L = \{\langle G \rangle | L(G) = \sum^{\star}\}$ and the question asks if it is co-RE. I know that if something is co-RE, it halts on every input not in L but may or may not ...
1
vote
1answer
35 views
Is the set of context free grammars that generate all words in co-RE?
Is $\{\langle G \rangle | L(G) = \sum^{\star}\}$ in co-RE? $\langle G \rangle$ is the encoding of a context free grammar. My intuition is that this is false.
2
votes
1answer
22 views
Does $\Sigma^* \cdot a^nb^n=\Sigma^*$
Is it true to say that $\Sigma^* \cdot$ {$a^nb^n: n>=0$} = $\Sigma^*$
Becuase if we take $\Sigma^*$ and concatenate it to {$a^nb^n: n>=0$} we don't get any "new" words than those we had in $\...
1
vote
2answers
108 views
Is it decidable that a context free language contains a given regular language?
I've been asked to solve this problem, but I'm completely stuck now.
Is the set $\{G \in\text{CFG} \mid L(G)\supseteq L(A) \}$ where A is DFA fixed beforehand decidable?
I know I've to find a ...
1
vote
0answers
12 views
What is the difference between the input set of a BSS RAM and a language?
I'm currently learning some things about BSS RAMs.
For sake of simplicity, please imagine them as a Turing machine over the reals.
Now, this machine gets some real numbers as input. The input values ...
0
votes
0answers
25 views
Building deterministic pushdown automaton for given grammar
I am trying to build a DPDA for the given grammar:
$S \to aR$
$R \to bRT \ |\ \varepsilon$
$T \to cSR \ |\ \varepsilon$
I tried simplifying grammar first (removing null and unit productions, ...
4
votes
1answer
133 views
Language that fulfills pumping lemma but is not in RE
I am supposed to find a language $$L\subseteq \Sigma ^*, \Sigma \subseteq \mathbb{N}$$ that fullfills the pumping lemma and is not in RE and not in coRE. I've never constructed a language with a given ...
0
votes
2answers
40 views
Halting problem of TM which recognize recursive languages is undecidable?
I am preparing for an exam and I came across this question in one of the tests.
Halting problem of Turing machines which recognize recursive languages
is undecidable. (True / False)
The solution ...
0
votes
0answers
18 views
How to prove that a language is sparse?
I have a decision problem. I feel like the problem has very limited expressive power so that it can not be NP-complete. What are the reasonable ways to try to prove the rough statement "it has limited ...
0
votes
0answers
20 views
Is this language context-free? $\Sigma$ = {a,b,#} L = {x1#x2#…#xk : k$\geq$2, every $x_i \in$ {a,b}* and xi $\neq$ xj for every pair i $\neq$ j} [duplicate]
Is this language context-free? $\Sigma$ = {a,b,#}, L = {x1#x2#...#xk : k$\geq$2, every $x_i \in$ {a,b}* and xi $\neq$ xj for every pair i $\neq$ j} I think it is not, because the PDA can't memorize ...
0
votes
1answer
13 views
Possible complement of $L =\{a^n b^{n+1} : n\geq0 \}$
The language was $L =\{a^n b^{n+1} : n\geq0 \}$.
This is my attempt:
I believed $L$ can also be expressed as:
$L =\{a^n b^{n}b : n\geq0 \}$
This implies that the number of $b$'s is always greater ...
0
votes
0answers
27 views
Context free grammar problem with hashtag
I am trying to solve the following context free grammar problem with hashtag approach but i can't figure it out. Can anyone help please?
Show a context-free grammar for the following languages:
$$\{w\...
1
vote
1answer
99 views
How the language $\{a^nb^mc^nd^m | n \geq1, \ m\geq1\}$ is used to check whether formal and actual parameters are equal?
How does the language $L=\{a^nb^mc^nd^m \mid n \geq1, m\geq1\}$ abstract the problem of checking that the number of formal parameters in the declaration of a procedure agrees with the number of actual ...
0
votes
0answers
27 views
What is the power of a Turing-machine that cannot write?
What is the power of a Turing-machine that cannot write?
So it can still read and go back and forth on the tape, but it cannot write.
I am wondering what this would be equivalent to in the ...
0
votes
1answer
19 views
LL(1) and LR(0) Grammars
The value in the parenthesis of language expressions signify how many next symbols are needed to make a decision.
For example, without reading a symbol from the input, we cannot decide in LL(1) ...
0
votes
1answer
36 views
Unrestricted grammar which generates $\{ a^1\#a^2\#a^3\#\dots \#a^k \mid k >0 \}$
I am looking for an unrestricted grammar which generates the following language:
$\{ a^1\#a^2\#a^3\# \dots \#a^k \mid k >0 \}$
That is, words like $a\#aa\#aaa\#aaaa\# \dots \# \text{$k$ times '$a$...
0
votes
1answer
77 views
Is this concatenation of two FA done right?
$r_3=r_1r_2=(a^*b)^*(a+ba)^*bb(a+b)^*$ comes out to be $r_3=r_2=(a+ba)^*bb(a+b)^*$ when i generate the resultant FA and its regex after concatenation i.e. it doesn't include $r_1$
Details:
Consider ...
1
vote
1answer
79 views
Exactly what is the difference between Finite Automata and Transition Graphs?
I haven't found a good enough answer by googling. Here's what i know:
TG's can have more than one initial state
In TG's, Edges/transitions can be labelled with strings
In TG's, it is not necessary to ...
