Questions tagged [formal-languages]
Questions related to formal languages, grammars, and automata theory
2,880
questions
2
votes
1
answer
39
views
FSA for 'closure' of a language; how to represent?
Is my interpretation of this correct?
I want to represent a regular language, L(B) as L(A*) where L(A*) represents the closure of L(B), as a DFA.
In order to do so, would I draw a new edge from the ...
- 77
1
vote
1
answer
25
views
Reachable States in a Product of Transition Systems
I am trying to deepen my understanding of transition systems and synchronization schemes and would appreciate some insights.
Consider the following scenario:
We have three transition systems A1, A2, ...
- 11
1
vote
1
answer
51
views
Splitting strings in pumping lemma for regular language
I was recently reading the book Introduction to the Theory of Computation, Second Edition by Michael Sipser, and encountered the following example:
Let $F=\{ww\ |\ w\in \{0, 1\}^*\}$. We show that $F$...
- 13
-1
votes
0
answers
44
views
Is the language of an equal number of as bs and cs context free?
The following question appears in my textbook.
Is the language, $L$, of all words over $Σ=\{a,b,c\}$ that have the same number of $a$'s $b$'s and $c$'s context free? $L = \{abc,\ cba,\ cbacab,\ ...
- 1
-1
votes
0
answers
25
views
Is the language of an equal number of as and bs followed by any number of cs context free?
Consider the language $L=\{a^n b^n c^m \mid n, m \in\{1,2,3\ldots\}\}$. Note that $n$ is not necessarily equal to $m$. Prove whether or not this language is context free.
I believe that it is context ...
- 1
1
vote
0
answers
31
views
Effect of slight modification to LL(1) parse table generation
I am experimenting with LL(1) parsers that do not use a separate lexer.
I have the following grammar:
S = (('<' S '>' | 'a'+) ' '?)+
The notation uses ' ...
- 11
1
vote
2
answers
35
views
Is garbage state necessary in DFA that enforces a particular input combination?
If I have the regex 1(0+1)* for example, then should my DFA have an arrow leading away from the starting state for when the first input is 0? I see that this regex enforces a 1 as the first input.
I ...
- 77
4
votes
1
answer
219
views
Is it possible to have intersection of L1 and L2 DFA contain states with no input edge?
I am doing a HW problem where I have L1 and L2.
I did the product construction method to produce all the new states of the DFA representing L1 and L2 (the number of states in L1 times the number of ...
- 77
7
votes
1
answer
321
views
Are Context-Free languages closed under XOR?
First, let's generalize the notion of XOR on strings over the ${0,1}$ alphabet. For strings of the same length, the XOR is the bitwise XOR. For strings of different lengths, we define $ \text{xor}(w, \...
- 73
0
votes
0
answers
16
views
Does a Moore Machine always require an output for start state?
My lecture notes show all moore machines as having an output even for q0, the starting state.
This video shows a Moore machine without an output for its starting state.
I understand that all Moore ...
- 77
1
vote
1
answer
82
views
How to formally prove that any regular expression can be written as a finite combination of base cases and operations?
In Michael Sipser's book, "Introduction to the Theory of Computation," regular expressions are defined as follows:
Based on this definition, how can I formally prove that any regular ...
- 113
1
vote
1
answer
45
views
Kleene star of any unary language is regular
I want to prove:
Let $L \subseteq \Sigma^*$.
If $\Sigma=\{a\}$, then $L^*$ is regular.
I found this answer:
Kleene star of an infinite unary language always yields a regular language.
But I do not ...
- 23
2
votes
1
answer
56
views
Counting words in an unambiguous context-free grammar
Given an unambigious context-free grammar $G = (\Sigma, V, \mathcal R, S)$, is there a polynomial-time algorithm that calculates $|L(G)|$ (including the case where $|L(G)|$ is infinite)?
The rough ...
- 21
0
votes
1
answer
60
views
Is the following language decidable?
Please confirm if my understanding of the below question, and my answer is correct.
Is the following language decidable? Justify your answer.
$L = \{\langle M_1,M_2\rangle \mid L(M_1) \cup L(M_2) = \...
- 103
0
votes
1
answer
30
views
