Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [formal-languages]

Questions related to formal languages, grammars, and automata theory

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 ...
2
votes
1answer
18 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
96 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
83 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
81 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
392 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
21 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 ...
1
vote
1answer
56 views

Why can't a left-recursive, non-deterministic, or ambiguous grammar be LL(1)? [closed]

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
36 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
35 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
121 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
17 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
21 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
108 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
20 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
37 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
43 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
23 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
45 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
120 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
36 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
37 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
25 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
199 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
16 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
31 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
143 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
50 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
45 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
30 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
16 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
37 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
105 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
30 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
26 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
38 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
99 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
326 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 ...
1
vote
1answer
79 views

Does this context-free grammar generate a regular language?

Does the following set of production rules produce a regular language or not? $S \to AB \mid b $ $A \to SB$ $B \to AS \mid a$ I have generated following words with above grammar $b , baa , baaaa , ...
0
votes
1answer
50 views

regex - difference between $\Lambda+(a+b)^*b$ and $(b+aa^*b)^*$

$r_1=\Lambda+(a+b)^*b$ $r_2=(b+aa^*b)^*$ $r_3=b+\$+aa^*b+(b+\$+aa^*b)(b+aa^*b)^*(b+\$+aa^*b)$ For this FA, which i think of as accepting "$\Lambda$ or anything ending in $b$", i came up with $r_1$, ...
0
votes
1answer
37 views

Can someone explain the language L = {w: w = uu, u \in La(1*01*)}

I need help understanding the language L above. These are my understanding: - w = uu is a concatenation of ...
1
vote
3answers
98 views

Prove a^4n b^m is irregular using puming lemma

My assignment is to prove that the language $L = \{ a^{4n} b^m \mid n > m >= 0\}$ is not a regular language. My first attempt was to prove that if if you set $a^l$ and $b^{l-1}$ you'd have an ...
5
votes
2answers
109 views

Is there any other computation theory besides the one in automata theory?

I'm a bit confused at a fundamental level. In Computer Science, maybe some of us mostly use discrete mathematics since our computer is digital (like during studying operating system, algorithms, ...
0
votes
2answers
139 views

Prove that a language is in co-NP

For a homework assignment, I have to prove that a given language $L \in coNP$. I understand that one way of doing so, would be to prove that $\bar{L} \in NP$, i.e. give a polynomial time verifier for ...
5
votes
3answers
220 views

DFA that rejects $a^{23}$ but accepts $\{a^i|i\geq 24\}$

Construct a DFA $M$ with $\Sigma = \{a\}$ and max. 11 states so that $a^{23}\not\in L(M)$ but $\{a^i|i\geq 24\}\subset L(M)$. I don't see how it is possible? Because it's a DFA and the alphabet only ...
1
vote
0answers
16 views

Notation for words with a common factor

Let $A$ be an alphabet and $u,v\in A^{*}$ be words. If it exists $z, u', u'', v', v'' \in A^{*}$ such as: $u = u'zu'' $ and $v = v'zv''$ then $z$ is a factor of both $u$ and $v$ (i.e. “common”). Is ...
10
votes
3answers
2k views

Why is there no permutation in Regexes? (Even if regular languages seem to be able to do this)

The Problem There is no easy way to get a permutation with a regex. Permutation: Getting a word $$w=x_1…x_n$$ ("aabc") to another order, without changing number or kind of letters. Regex: Regular ...
0
votes
1answer
33 views

Find a grammar for this language

Assume the language: $$L=\left\{w\in\{0,1\}^*\,| \text{ w has odd length and 111 right in the middle}\right\}$$ This is my attempt for constructing a grammar $G$ for this language: $$G: S \...
3
votes
1answer
57 views

Do multiple transitions over the input give finite state machines more power?

In the common model of FSA, the automaton reads the input string once, moving from one state to another after reading each letter in the input string. Epsilon transitions allow moving from one state ...