Questions tagged [formal-languages]
Questions related to formal languages, grammars, and automata theory
0
votes
2answers
25 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
15 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
17 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 ...
-1
votes
0answers
54 views
prove that the language {x y x^R | x, y ∈ {a, b} ∗} is context free [duplicate]
If yes, please explain how we can write grammar or create a PDA for it. If not a CFL, then prove it through pumping lemma.
0
votes
1answer
11 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
17 views
Is it possible to enumerate all strings of a Recursively Enumerable language (but non recursive) in some order?
In case of recursive languages, generate each string in some order (say alphabetically) and give it to respective TM, if it halts at a final state then string is present in language, otherwise not. ...
0
votes
0answers
24 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
92 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
5 views
LL(1), Compilers, Formal Language [duplicate]
Is it possible to construct LL(1) grammar for every DCFL?
0
votes
0answers
25 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
0answers
8 views
converting automaton into dfa and finding the language it accepts [closed]
i am trying to practice converting into minimal FDA and finding the language it supports. could you please check if i did correctly and correct me if i've done any errors?
basic digraph:
after ...
0
votes
1answer
16 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
29 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
73 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
34 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
50 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
0answers
16 views
Follow Set of a Grammar
I have a grammar, and I cannot make sure a follow set:
A -> ABC
B -> b
C -> c
...
0
votes
1answer
46 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
29 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
73 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 ...
0
votes
0answers
12 views
Is there a Context-free grammar for a^(n^2) [duplicate]
The language was L1 = {a^(n^2) : n>=0}. I knew a^(n^2) can also be expressed as a^(nn). I ...
4
votes
2answers
90 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
52 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
194 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 ...
0
votes
0answers
35 views
Is this language with fewer b's than twice the number of a's regular?
Is $\{a^{2n}b^m|0\leq m< n\}$ regular? The lecturer said it is not and referred to the pumping lemma but isn't 2 the pumping length?
For every $n>m$ you can choose $u=\epsilon$, $v=aa$, $w$ the ...
0
votes
0answers
126 views
Reduction from membership problem
i'm preparing for my exam from Formal languages and automata and i've found one example, which i don't know, how to deal with it.
I've a language A with some rules and i need to prove using reduction ...
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
27 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
45 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 ...
0
votes
0answers
19 views
Choice of $x,y,z$ when applying the pumping lemma [duplicate]
I want to determine whether
$$L=\big\{0^i \, 1^j \big| \,i,j \geq 1, \, i\neq j \big\}$$
is a regular language or not.
Attempt:
Let's assume that $L$ is regular. Then for $p=5$, the string $s \in ...
0
votes
1answer
29 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.
...
0
votes
0answers
26 views
Given a regular language L and only given an NFA that accepts it , is this enough to say that the complement of L is also regular?
"Given a regular language L and only given an NFA that accepts it then L'(the complement) is also regular"
Is this good enough proof to say that the complement is regular?
I keep being told this ...
0
votes
0answers
9 views
Prove that the grammar in Chomsky Normal Form is not Regular [duplicate]
S-> BS|a
B-> CB|b
C-> SC|c
I am stuck with this problem. Can someone please help me to approach this?
2
votes
1answer
30 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
30 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 ?
0
votes
0answers
18 views
Merging nonterminals of a Context-Free Grammar?
I am reading through a paper on grammatical inference and stumbled upon the following:
Given positive example w, we first construct the tabular
representation T(w) and the primitive CFG G(T(w)), ...
1
vote
0answers
17 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
30 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
34 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
votes
0answers
23 views
How to modify this CFG to use the conjunction (and) for two sentences?
I wrote the following CFG to parse sentences such as (tom ate pizza), (bill ate rice)...etc.in PROLOG.
s(s(NP,VP))-->np(NP),vp(VP).
vp(vp(VBD,NP))-->vbd(VBD),np(NP).
np(np(NN))-->nn(NN).
np(np(NNP))-...
1
vote
1answer
36 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
16 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
42 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
24 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 ...
0
votes
0answers
23 views
Is the following language regarding P=NP/P!=NP decidable? [duplicate]
Let A = {w|w $\in$ {0,1}, such that
w=0 iff P=NP
w=1 iff P!=NP
Would the language itself be decidable?
1
vote
2answers
199 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
14 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}$ ...
1
vote
0answers
58 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
45 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 ...
