Questions related to formal languages, grammars, and automata theory

learn more… | top users | synonyms (1)

10
votes
2answers
213 views

Algorithm to test whether a language is context-free

Is there an algorithm/systematic procedure to test whether a language is context-free? In other words, given a language specified in algebraic form (think of something like $L=\{a^n b^n a^n : n \in ...
2
votes
2answers
24 views

Method for measuring the 'similarity' between FSA grammars?

I'm working with a pattern matching algorithm that generates an acyclic finite state automaton that accepts a given text string and all its substrings. The FSA algorithm is being run on a symbolic ...
7
votes
1answer
154 views

Is there a strictly non-deterministic one-counter language whose complement is one-counter?

Let $A= \{L \mid L \;\text{is one-counter and \(\bar{L}\) is also one-counter} \}$ Clearly, $\text{Deterministic one-counter} \subseteq A$ Is it the case that $ A = \text{Deterministic ...
6
votes
1answer
199 views

Can this CFG be written into an equivalent LL(1) grammar?

I have the following CFG which I suspect cannot be rewritten to one which is LL(1): $S \rightarrow \epsilon\ |\ aSbS\ |\ bSaS\ |\ cSdS\ |\ dScS$ I've thought about it for a while, and can't seem to ...
4
votes
1answer
110 views

Counting the number of words accepted by an acyclic NFA

Let $M$ be an acyclic NFA. Since $M$ is acyclic, $L(M)$ is finite. Can we compute $|L(M)|$ in polynomial time? If not, can we approximate it? Note that the number of words is not the same as the ...
-2
votes
1answer
32 views

Prove that $(L^*M^*)^* = (L\cup M)^*$

I would like to find out how to prove this statement. Thank you. Well I think that I proved one part of the statement, but my proof doesn't really look elegant. My proof of $(L\cup M)^* \subset ...
-3
votes
1answer
96 views

Pushdown Automata Challenge

I read one old-midterm exam on Automata. consider: the language that accepted by above pushdown automata is not generated by which of the following grammar? 1) S->aBaa|a$\epsilon$ ...
16
votes
0answers
361 views

Is there a regular tree language in which the average height of a tree of size $n$ is neither $\Theta(n)$ nor $\Theta(\sqrt{n})$?

We define a regular tree language as in the book TATA: It is the set of trees accepted by a non-deterministic finite tree automaton (Chapter 1) or, equivalently, the set of trees generated by a ...
7
votes
0answers
88 views

Test whether two languages are equal, when give in algebraic form

This sub-problem is motivated by Algorithm to test whether a language is regular. Suppose we have two languages $L_1,L_2$ that are expressed in "algebraic" form, as formalized below. I want to ...
6
votes
0answers
119 views

When did $LR(k)$ acquire the meaning “left-to-right scan, rightmost derivation?”

According to the Wikipedia article, the L in $LR(k)$ means "left-to-right scan", and the "R" means "rightmost derivation." However, in Knuth's original paper on $LR(k)$ grammars, he defines $LR(k)$ ...
5
votes
0answers
82 views

Expressiveness of modern regular expressions

I recently discussed with a friend about a website that proposed regex challenges, mainly matching a group a of words with a special property. He was looking for a regex that matches strings like ...
5
votes
0answers
147 views

How to disambiguate symbolic regular expressions

What I mean by a "symbolic regular expression" (if there already is a different name for this I'm not aware of it) is a regular expression that may include exponents that are symbolic arithmetic ...
3
votes
0answers
66 views

What are appropriate isomorphisms between formal languages?

A formal language $L$ over an alphabet $\Sigma$ is a subset of $\Sigma^*$, that is, a set of words over that alphabet. Two formal languages $L$ and $L'$ are equal, if the corresponding sets are ...
3
votes
0answers
55 views

Prove or disprove that every $L$ in this class is a CFL iff $L$ is equivalent to a substitution

Let $L$ be a language with every string of the form $(w_i\#)^*$ with $w_i\in\{0,1\}^*$. Set $w'\sim w$ if there is a permutation $\pi_1$ such that $w_i=w'_{\pi_1(i)}$ for all $i$. If additionally ...
2
votes
0answers
96 views

Good introductions to Formal Language Theory and Formal Grammars

Does anyone know any good introductions to Formal Language theory and Formal Grammar, that cover the mathematical basis of Syntax and things like context free grammars and pushdown automata. In ...
2
votes
0answers
133 views

Prove Single-Tape and Non-write Turing Machine can Only Recognize Regular Language?

Here is the problem: Prove the single-tape TM that cannot write on the portion of the tape containing the input string recognize only regular language. My idea is to prove that this particular TM ...
2
votes
0answers
41 views

What kind of structural features of strings can be described by regular grammars?

Context-free grammars, as well as other types of grammars, can naturally associate structure with the strings of the defined language, for example tree structures in the case of context-free language. ...
2
votes
0answers
85 views

Example of execution fragment of multi-process transition system

Here is a simple transition system of beverage vending machine: The exemplary execution fragments can look like this: Now, imagine we have multi-process TS where processes are identical and ...
2
votes
0answers
216 views

Intuitive description for training of LSTM (with forget gate/peephole)?

I am a CS undergraduate (but I don't know much about AI though, did not take any courses on it, and definitely nothing about NN until recently) who is about to do a school project in AI, so I pick a ...
2
votes
0answers
65 views

The grammar of the GeoQuery language

GeoQuery is a dataset used for benchmarking semantic parsers. It contains 880 queries about USA geography. The queries are in Prolog format, for example: ...
2
votes
0answers
63 views

Computational power of nondeterministic type-2 min-heap automata

I have asked a series of questions concerning capabilities of a certain class of exotic automata which I have called min-heap automata; the original question, and links to others, can be found here. ...
1
vote
0answers
36 views

Is this theorem about left-factored grammars correct?

I am working on CFG grammars, LL grammars in particular and I encountered the following theorem in the slides of presentations written by my professor: A CFG grammar cannot be left-factored if all ...
1
vote
0answers
75 views

Flowcharts vs DFA resp FSM equivalency

First I apologize if I confused therms DFA and FSM, to me it seems that is the same thing. The question is simple: Are the flowcharts (sequence, branching and jumping) equivalent to DFA resp. FSM? I ...
1
vote
0answers
82 views

Correct approach to Mapping Reduction from $E_{TM}$

as the title states, I am trying to figure out if my approach to solving mapping reduction from $E_{TM}$ to some other language is correct. As you surely know, $E_{TM} = \left \{ < M> \mid M \ ...
0
votes
0answers
42 views

Find the language generated by a grammar

I have to find the language generated by the grammar: $\qquad\begin{align*} S &\to SA \mid a \\ A &\to aAa \mid bA \mid \varepsilon \end{align*}$ where $\varepsilon$ is the empty ...
0
votes
0answers
53 views

Is this a grammar for arithmetic expressions?

Describe the language generated by the following grammar <A> ::= <A><A> '+' | <A><A> '*' | 'a' So it's not too hard to see ...
0
votes
0answers
42 views

Write grammars rule to translate general boolean expressions in Prodocut Of Sums

Given a standard grammar describing the boolean expression with AND, OR and NOT operators: ...
0
votes
0answers
61 views

Does this CFG produce this language?

I missed a question about a CFG on an assignment, but the grader wouldn't explain what was wrong with my answer and instead provided me the answer from the book. Here is the language: ...